3SAT____Problems


#1

What is 3-SAT and how do you prove that 3-SAT is NP-complete??


#2

Let us start from your question so what is meant by a 3-SAT problem or a SAT problem in general. It is basically the satisfiability problem which means for example :
Say that you have a Boolean expression which is written using only NOT, AND, OR, variables and parentheses. The SAT problem states as : given a particular expression is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true. For example,

x1∧x2∨x3

SAT problem for this particular expression would be: Is there some values of x1,x2,x3 such that given Boolean expression is TRUE.
Remember that the answer to SAT problem is only YES or NO. We do not care much about what’s the value. Just the existence of such values is a must.

If you understood this then let’s go further.

3-SAT problem is a special case of SAT problem where Boolean expression should have very strict form that is it should be divided to different clauses such that every clause contains of exactly three literals. For example,

(x1∨x2∨x3)∧(x4∨x5∨x6)

This Boolean expression in 3-SAT form with 2 clauses where each clause contains precisely 3 literals. The question remain’s the same. Is there such values of x1 to x6 such that given Boolean expression is TRUE.

If you understood this properly then solve this question for fun(and practice) :sunglasses:

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.


#3

Given a set of boolean variables: x1, x2…

We’ll define a literal to be either a variable xi or NOT xi.
and a clause to be a 3 literals OR’d together, e.g. (x1 OR (NOT x4) OR x5)

A 3-SAT problem is a “conjunction of clauses” of the form:
(x1 OR x2 OR x4) AND
(x3 OR (NOT x4) OR x7) AND

Solving a 3-SAT problem is the act of finding a set of variable assignments to True or False that make that statement true or alternately providing a proof that no such set of variable assignments can exist.
3-SAT is interesting precisely because solving 3-SAT is “as hard as” solving any other problem in NP, and 3-SAT is in NP, which means 3-SAT is “NP-complete”.

proving 3SAT is NP-complete:

Given a set of clauses C1, C2, . . . , Cm in CNF form, where Ci contains literals from
x1, x2, . . . , xn problem is to check if all clauses are simultaneously satisfiable. Cook-Levin theorem shows
that SAT is NP-Complete.
3SAT problem
¯
:- Given a set of clauses C1, C2, . . . , Cm in 3CNF from variables x1, x2, . . . , xn problem is to
check if all the clauses are simultaneously satisfiable.
3SAT := {Satisfiable 3CNF formulae }
Proof Sketch:3SAT problem is in NP since any assignment of values to variables can be verified in polynomial
time. We show that 3SAT is also NP-Complete by showing a reduction from SAT to 3SAT in polynomial
time.
Proof Sketch:3SAT problem is in NP since any assignment of values to variables can be verified in polynomial
time. We show that 3SAT is also NP-Complete by showing a reduction from SAT to 3SAT in polynomial
time.
SAT ≤p 3SAT

We reduce each clause of the SAT instance containing more than 3 literals into a conjunction of several new
clauses in 3SAT instance as follows:

  1. Create a new clause for 3SAT instance containing first two literals of corresponding SAT instance clause
    and OR it with a free variable say z
  2. Make new clause in conjunction with previous clause and add the next literal of SAT instance clause and
    OR it with ¯z1 i.e. negation of free variable used in previous clause and OR it with a new free variable say z2
  3. Repeat step 2 with next clause in conjunction with previous clause containing next literal of original
    CNF clause OR with ¯z2 and further ORed with z3.Continue this process till last two literals in original SAT
    instance clause will be left. Last clause will contain negation of free literal of previous clause ORed with last
    two literals in corresponding clause in SAT instance.
  4. Repeat step 1 to 3 for next SAT instance clause and keep the output in conjunction with previous 3SAT
    instance clauses.

Hence if a particular SAT instance clause contain m literals where m > 3 then the reduced 3SAT instance
will contain m − 2 clauses in conjunction and contain m − 3 free variables. So, this reduction is polynomial
in time and space.