Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I don't get the 3SAT problem.

Can someone explain the 3SAT problem as if I were 5 years old, ideally with examples?


share|cite|improve this question

closed as too broad by Austin Mohr, graydad, Solid Snake, dtldarek, Claude Leibovici Sep 22 '15 at 7:02

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

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. – Mariano Suárez-Alvarez Nov 28 '11 at 4:55

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.

share|cite|improve this answer
Is there a difference between SAT and 3SAT problems? (other than the 3 literals requirement) – kuhaku Dec 13 '15 at 20:52

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.

share|cite|improve this answer

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.