What is the $3$-SAT problem? [closed]

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.

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.

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!

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.