Satisfiability of Boolean expressions (SAT) is NP-complete

SAT = Satisfiability of Boolean expressions: given arbitrary Boolean expression E over the variables x1, x2, .. , xd, is there an assignment of truth values to the x1, x2, .. which makes E true?

This doesn’t matter what Boolean operators take place, conventionally one considers and ∧, or ∨, Not ¬.

SAT is a prototypical ‘hard problem’. That is, the problem which is usually proven to be NP-complete ‘from scratch’, where after all other problems to be confirmed NP-complete are reduced to SAT. The theory of NP-completeness start with the key theorem (Cook 1971):  SAT is NP-complete.

Given this central role of the SAT is helpful to build up an intuitive understanding of the nature of problem, comprising details of measurement and ‘simple’ versions of SAT.

A) This doesn’t matter what Boolean operators take place, conventionally one considers And ∧, Or ∨, Not ¬. Special forms, example: CNF

B) The length n of E can be evaluated by the number of characters of E. This is more convenient, though, to first remove “Not-chains” ¬¬¬ ..  By using the identity ¬ ¬ x = x, and to evaluate the length n of E by the number n of occurrences of variables (d represents the number of distinct variables x1, x2, .. xd in E, d ≤ n). This is convenient to ignore mentioning the unary operator ¬ explicitly by introducing, for each and every variable x, its negation ¬ x as a dependent variable. The variable and its negation are termed as literals. Therefore, an expression E with d variables consists of 2d distinct literals which might take place in E.

C) Any Boolean expression E can be computed in linear time. Given truth values for x1, x2, .. xd, the n occurrences of literals are leaves of a binary tree with n -1 internal nodes, each of which symbolizes a binary Boolean operator. The bottom-up computation of this tree needs n-1 operations.

D) Satisfiability of expressions over the constant number d of various variables can be decided in the linear time. By trying all 2d assignments of truth values to variables, the SAT can be decided in time O(2d n), a bound which is linear in n and exponential in d. When we consider d constant, 2d is as well a constant - therefore this version of the satisfiability problem can be resolved in linear time! This argument exhibits that, when SAT turns out to be a hard problem, this is due to an unbounded growth of the number of various variables. Certainly, when d grows proportionately to n, the argument above outcomes an exponential upper bound of O(2n).

E) In order to state SAT as a language, select an appropriate alphabet A and a coding scheme which assigns to any expression E a word code(E) ∈ A*, and define: SAT = {code(E)| E is a satisfiable Boolean expression}

Theorem (Cook 1971):  SAT is NP-complete - the key theorem at origin of all the other NP-complete outcomes.

A) SAT is in NP. Given E and an assignment of the truth values as a certificate of satisfiability, that is, the truth value of E can be evaluated and verified in the linear time.

B) Idea of proof that SAT is a NP-hard.  Suppose L is any language ∈ NP, we have to verify L ≤p SAT. L ∈ NP signifies there is a deterministic polynomial-time verifier M with L = L(M). We build in polynomial time a Boolean expression E = E(M, w) with property that w ∈ L iff E is satisfiable. The perception is that E(M, w) simulates, that is, explains, the computation of M on w step by step. Though E is ‘big’, a detailed analysis exhibits that the length |E| of E is polynomially bounded in length |w|, and furthermore, that E can be evaluated in time polynomial |w|.

The given idea guides the construction of E(M, w). The computation of M on any word w is the sequence of configurations, where a configuration comprises the state of tape, the state of M, and the position of M’s read or write head on the tape. This sequence can be explained, or modeled, by a (big) set of Boolean variables.

For illustration, we introduce a variable (99, 1) that we want to be true if and only if after 99 steps M is in state 1. The transition from step 99 to step 100 can be modeled by some expression which relates all the variables included, like t(99, 0), that we want to be true if and only if after 99 steps M is reading symbol 0 on its tape. Therefore, the behavior of any TM M on w can be modeled by a big expression that is true if and only if M accepts w. QED.

Satisfiability stays NP-complete even when we restrict the class of Boolean expressions in different ways. The standard and suitable normal form, which still permits us to state any given Boolean function, is the conjunctive normal form, CNF.

Definition: The CNF expression E is a conjunction of clauses Ci, where each and every clause is disjunction of literals Lj, and a literal is a single variable or negation of a single variable, example: x: E = C1 ∧ C2 ∧ C3 ∧ ... where Ci = ( L1 ∨ L2 ∨ L3  ∨ ..) and Lk = x or Lk = ¬x.

Any Boolean expression E can be converted to an equivalent expression in CNF by using the identities:

a) De Morgan’s law: ¬ (x ∧ y) = ¬ x ∨ ¬ y, ¬ (x ∨ y) = ¬ x ∧ ¬ y 
b) Distributive law: x ∧ ( y ∨ z ) = (x ∧ y) ∨ (x ∧ z), x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)

Suppose CNF be the problem of deciding the satisfiability of CNF expressions. As SAT is NP-complete and any Boolean expression E can be converted to an equivalent expression F in CNF, it is apparent that SAT is reducible to the CNF, and it is plausible to conjecture which SAT ≤p CNF, and therefore that CNF is NP-complete. The conjecture is accurate, however the plausibility is very simple minded. What is wrong with the given ‘pseudo-proof’? In order to confirm SAT ≤p CNF, convert any given Boolean expression E in random form into an equivalent CNF expression F; E is satisfiable if and only if F is satisfiable. ‘QED’.

Error in the argument above is unseen in the letter ‘p’ in ‘≤p’ that we defined as a polynomial-time reduction. The transformation of a random Boolean expression E to an equal CNF expression F might cause F to be exponentially bigger than E, and therefore to need time exponential in the length of E just to write down the outcome! Witness the given formula E in disjunctive normal form (DNF):E =  x11 ∧ x12  ∨  x21 ∧ x22  ∨  x31 ∧ x32  ∨  ...  ∨  xn1 ∧ xn2

This comprises of 2n literals each of which seems just once, therefore it consists of length 2n as measured by the number of occurrences of literals. Repeated application of the distributive laws outcomes:

F = ∧(j1  .. jn  = 1,2) (x1j1  ∨  x2j2  ∨   x3j3   ∨ ...  ∨ x njn)

F is an AND of 2n clauses, where each and every clause consists of exactly one variable xj for j = 1 .. n, with the second index selected independently of the selection of all other second indices. Therefore, the length of F is n 2n, a transformation which can’t be completed in polynomial time.

We will now give a correct proof which CNF is NP-complete, as a result of the stronger assertion that 3-CNF is NP-complete.
Definition: The 3-CNF expression is the special case of CNF expression where each and every clause has three literals (‘precisely 3’ or ‘at most 3’ is similar - why?).

Because of its limited form, 3-CNF is conceptually easier than SAT and therefore it is simpler to reduce it to new troubles that we aim to verify NP-complete. We aim to exhibit that 3-CNF is NP-complete by decreasing SAT to 3-CNF, that is, SAT ≤p 3-CNF. In contrast to the argument employed in the wrong proof above, that failed since it avoids exponential lengthening, the given construction keeps the length of F short by utilizing the trick that E and F require not be equal as Boolean expressions!

Theorem: 3-CNF SAT is NP-complete

Proof idea: Deduce SAT to 3-CNF SAT, SAT ≤p 3-CNF SAT. To any Boolean expression E we assign the polynomial time a 3-CNF expression F which is equivalent in the weak sense that either both E and F are satisfiable or neither is. Note that E and F require not be equivalent as Boolean expressions, that is, they need not represent similar function! They just behave similar with respect to satisfiability.

Given E, we build F in 4 steps, described by using the illustration E = ¬ (¬ x ∧ (y ∨ z))

A) Employ de Morgan’s law to push negations to the leaves of expression tree:

E1= x ∨ ¬ (y ∨  z) = x ∨ (¬ y ∧ ¬ z)

B) Assign a new Boolean variable to each and every internal node of the expression tree, that is, to each occurrence of an operator, and utilize the Boolean operator ‘equivalence’ ⇔ to state the fact that this variable should be the result of the corresponding operation: u ⇔ (¬ y ∧ ¬ z), w ⇔ x ∨ u

C) Build an expression E2 which states that the root of expression tree should be true, traces the evaluation of the whole tree, node by node, and joins all such assertions by using ANDs:

E2 = w ∧ (w ⇔ (x ∨ u)) ∧ (u ⇔ (¬ y ∧ ¬ z)).

E2 and E are equal in the weak sense of concurrent satisfiability. When E is satisfiable, then E2 is as well, by simply assigning to the new variables u and w the outcome of the corresponding operation. On the contrary, when E2 is satisfiable, then E is as well, employing similar values of the original variables x, y, z as appear in E2.

Note that E2 is in conjunctive form at outermost level; however its sub expressions are not, therefore we need a last transformation step.

D) Recall the Boolean identity for the implication: a ⇒ b = ¬ a ∨ b to derive the identities:

a ⇔ (b ∨ c) = (a ∨ ¬ b) ∧ (a ∨ ¬ c) ∧ (¬ a ∨ b ∨ c)
a ⇔ (b ∧ c) = (¬ a ∨ b) ∧ (¬ a ∨ c) ∧ (a ∨ ¬ b ∨ ¬ c)

Using such identities on the sub expressions, E2 gets converted to F in 3-CNF:

F = w∧ (w ∨ ¬ x) ∧ (w ∨ ¬ u) ∧ (¬ w ∨ x ∨ u) ∧ (¬ u ∨ x) ∧ (¬ u ∨ z) ∧ (u ∨ y ∨ z)

Each of four transformation steps can be completed in linear time and lengthens the expression by utmost a constant factor. Therefore, the reduction of a Boolean expression E in common form to one, F, in 3-CNF can be completed in polynomial time. QED

Note the critical role of integer ’3’in 3-CNF: we require expressing the outcome of a binary operator, like w ⇔ x ∨ u, that naturally includes three literals. Therefore, it is no surprise that the method utilized in the proof above fails to work for the 2-CNF. Certainly, 2-CNF is in P.

In analogy to CNF we state the disjunctive normal form DNF as an OR of terms, each of which is the AND of literals: E = T1 ∨ T2 ∨ T3 ∨ ... Here Ti = (L1 ∧ L2 ∧ L3 ∧..)

Note: DNF-SAT is in P, however DNF-SAT can be decided in the linear time (consider xy’z ∨ x x’ ∨...).

Does this signify that the NP-completeness of SAT is just a matter of representation? No!

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.