48
$\begingroup$

In the hopes of improving my knowledge on the question, could someone outline the inputs and outputs for the 3-SAT problem? It would also be helpful if you could express how this problem differs in structure to SAT, 2-SAT or 4-SAT problems.

$\endgroup$
2
  • 21
    $\begingroup$ This site is not best used by saying "please explain X to me". Indeed, and to begin with, that is not really a question. But more importantly, it should not be difficult to find several explanations of what 3SAT is, some of which are surely adorned with examples (and there are textbooks and other sources, too, of course) Have you tried reading, say, Wikipedia? What in the exposition there you do not understand? Etc. $\endgroup$ Nov 28, 2011 at 4:55
  • 3
    $\begingroup$ It's a shame this has been closed as some editing could have saved this question. The famous "How do JavaScript closures work?" question on SO was initially posted as asking to explain it to a 6-year-old. stackoverflow.com/revisions/111102/1 $\endgroup$
    – Brian Risk
    Jul 18, 2016 at 14:04

3 Answers 3

91
$\begingroup$

I would start from the question, what's SAT in general. SAT is satisfiability problem - say you have Boolean expression written using only AND, OR, NOT, variables, and parentheses. The SAT problem is: given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?

For example,

$x_{1} \wedge x_{2} \vee x_{3}$

SAT problem for this Boolean expression: is there such values of $x_{1},x_{2},x_{3}$, that given Boolean expression is TRUE. The answer to SAT problem is only YES or NO. We don't care what's the values of $x_{1},x_{2},x_{3}$, just existence of such values.

If this is OK, let's go further.

SAT3 problem is a special case of SAT problem, where Boolean expression should have very strict form. It should be divided to clauses,such that every clause contains of three literals.

For example,

$(x_{1} \vee x_{2} \vee x_{3}) \wedge (x_{4}\vee x_{5} \vee x_{6})$

This Boolean expression in 3SAT form, 2 clauses, each clause contains of 3 literals. The question is the same, is there such values of $x_{1}...x_{6}$, that given Boolean expression is TRUE.

If it wasn't helpful. I would advise to at look at application of SAT and 3SAT problem that close to your field of studying.

$\endgroup$
1
  • 2
    $\begingroup$ Is there a difference between SAT and 3SAT problems? (other than the 3 literals requirement) $\endgroup$
    – shinzou
    Dec 13, 2015 at 20:52
70
$\begingroup$

There are a bunch of teddy bears A, B, C, D and so on that are red on one side and blue on the other! (You choose how to color them)

AND there are a bunch of 3 armed aliens with really long arms. Each alien grabs 3 teddy bear hands! (A teddy bear hand can be grabbed by more than one alien.)

3-SAT is the problem of whether you can color the teddy bears such that every alien is holding at least one blue hand!

enter image description here

$\endgroup$
3
  • 12
    $\begingroup$ You are brilliant David M!!! Simply epic! You should be proud of yourself $\endgroup$ Mar 6, 2018 at 16:55
  • $\begingroup$ I. Love. This. A+ $\endgroup$
    – Greenstick
    Sep 13, 2018 at 20:04
  • 1
    $\begingroup$ Shouldn't it be "each alien grabs 3 different teddy bear hands"? $\endgroup$
    – Jus12
    Apr 12, 2019 at 6:38
26
$\begingroup$

Start with a bunch of variables $x_1,x_2,\dots$ that, instead of taking on real values, only take on values from the set, $\{{{\rm true,\ false}\}}$. If $a,b$ are such variables then $a\vee b$ is true unless $a$ and $b$ are both false (think, "or"); $a\wedge b$ is true only if both $a$ and $b$ are true (think "and"); $-a$ is true if and only if $a$ is false (think "not").

A clause is a disjunction of variables, that is, something of the form $x_{i_1}\vee x_{i_2}\vee\cdots\vee x_{i_n}$, where some of those variables could be negations of other variables (that is, a clause could be somehting like $x\vee-y\vee z$). It's easy to tell whether a clause is satisfiable, that is, whether there are values of the variables that make it true.

The satisfiability problem is this: given a (finite) collection of clauses, is there a way to assign values to the variables to make all the clauses true?

3SAT is the case where each clause has exactly 3 terms.

EDIT (to include some information on the point of studying 3SAT):

If someone gives you an assignment of values to the variables, it is very easy to check to see whether that assignment makes all the clauses true; in other words, you can efficiently check any alleged solution.

If someone asks you whether there is a way to assign values to the variables to make all the clauses true, then you could just try all possible assignments of values, and check each one. But since there are two possible assignments to each variable, there are $2^k$ possible assignments of values (where $k$ is the number of variables), and this grows very large very fast. The big question is whether there is a cleverer way to do things so that you can solve the problem in a number of steps polynomial in the size of the problem, as opposed to exponentially many steps in the naive approach.

No one knows. What is known is that if there is an efficient algorithm for solving 3SAT, then there is an efficient algorithm for solving EVERY problem for which alleged solutions can be tested efficiently.

$\endgroup$
3
  • $\begingroup$ Does a 3SAT instance need to have exactly three instances in each term? is (x \/ ~y ) /\ (~x \/ y \/ ~z) valid. if you have no variables for one of the terms, like in the first clause, how can one handle this ? $\endgroup$
    – nixon
    Apr 27, 2018 at 10:48
  • 1
    $\begingroup$ If a clause doesn't have three variables in it, say it's $a\vee b$, you can always replace it with $a\vee b\vee b$, without changing the satisfiability of the conjunction of all the clauses. $\endgroup$ Apr 27, 2018 at 12:15
  • $\begingroup$ A +1 because ure the only one who said only finite number of clauses $\endgroup$ Jan 17, 2022 at 14:39

Not the answer you're looking for? Browse other questions tagged .