Take the 2-minute tour ×
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.

I don't get the 3SAT problem.

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

Thanks!

share|improve this question
9  
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
1  
@nubela, Please consider accepting answers that you like on your questions, as you haven't accepted a single answer in all your questions... –  sxd Nov 28 '11 at 18:42

2 Answers 2

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|improve this answer

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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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