NP Completeness- SAT, CLIQUE (Part-2)

 

First NP-complete Problem

•While the definitions for the categories of problems is easily understood, the remaining question is……Are there any NP-complete problems?

•The answer (surprisingly) is YES. One problem proven to be NP-complete is known as circuit Satisfiability.

•Circuit Satisfiability problem is first NP Complete problem.

CIRCUIT-SAT

•A Boolean circuit is a circuit of AND, OR, and NOT gates; the CIRCUIT-SAT (circuit Satisfiability) problem is to determine if there is an assignment of 0’s and 1’s to a circuit’s inputs so that the circuit outputs a 1 (is satisfied).

•Formal proof that circuit Satisfiability is NP-Complete requires technical detail beyond the scope of this text.

•Sketch of Proof

•Clearly we see that the problem is in NP since given a particular set of inputs we can compute the result of the circuit in polynomial time.

•The difficulty is showing that ANY problem in NP can be represented as a circuit Satisfiability problem.
•This is shown by considering any computable algorithm can be represented by a logical circuit that can be encoded into a state machine on a general purpose computer.
•The operation of the algorithm simply transitions between states in the computer. At some point, one of the bits in the computer will represent the output of the algorithm and thus any algorithm can be reduced to a circuit Satisfiability problem (in polynomial time).

Problems in P and NP

 •Many seemingly similar problems often are in different classes. One version has a polynomial time solution and is thus in P, while only a minor modification to the description makes the variant NP-complete. For example:

Boolean Satisfiability
•Problem
A Boolean expression is a formula composed of
1.n Boolean variables x1, x2, ..., xn
2.m Boolean operations consisting of ∧ (logical AND), ∨ (logical OR), ¬ (logical NOT), → (logical implication), and ⇔ (logical if and only if)
3.Parentheses
–Parentheses delineate clauses that consist of a group of variables that are connected by operands.
•Can we assign 0’s and 1’s to the variables so that Boolean expression is 1.
•SAT = {(Φ) : Φ is a Satisfiable Boolean formula }
•Example:
                 ((x1 ®x2) Ú Ø((Øx1 « x3) Ú x4)) ÙØx2
•    Has Satisfying assignment {x1 = 0, x2 = 0, x3 = 1, x4 = 1}, since
Φ =  ((0 ®0) Ú Ø((Ø0 « 1) Ú 1)) ÙØ0
    = (1 Ú Ø((1« 1) Ú 1))
    = 1
• Thus formula Φ belongs to SAT.
•

•It can be shown that Boolean Satisfiability is NP-complete by reducing circuit Satisfiability to Boolean Satisfiability.

Satisfiability of Boolean Formula is NP-Complete

•Using circuit Satisfiability as the initial NP-complete problem, we can show that Boolean Satisfiability is NP-complete by reducing any instance of circuit Satisfiability to Boolean Satisfiability.

•Proof :
•SAT belongs to NP
–Given a satisfying assignment, the verification algorithm replaces each variable with its value and evaluates the formula, in polynomial time.
•SAT is NP-Hard (Show CIRCUIT-SAT £p SAT).
•CIRCUIT-SAT £p SAT i.e. , any instance of circuit Satisfiability can be reduced in polynomial time to an instance of formula Satisfiability .

•Intuitive Induction:
–Look at the gate that produces the circuit output.
–Inductively express each of gates inputs as formulas.
–Formula for the circuit is then obtained by writing an expression that applies the gate’ function to its input formulas.

•Unfortunately this is not polynomial reduction.

–Shared formula the gate whose output is fed to 2 or more inputs of other gates cause the size of generated formula to grow exponentially.

Incorrect Reduction:
x10    = ( x7 Ù x8 Ù x9)
= ( x1 Ù x2 Ù x4) Ù (x5 Ú x6) Ù (x6 Ú x7)

= ( x1 Ù x2 Ù Øx3) Ù( Øx4 Ú( x1 Úx2)) Ù( Øx4 Ú( x1 Úx3)) Ù x4

•      While it would seem intuitive to simply write the Boolean expression for the circuit, this cannot necessarily be done in polynomial time if the gates have fan-out greater than two (i.e. the output of one gate goes to the input of more than 2 other gates).

•     Instead what we do is represent each wire in the circuit by a Boolean variable  xi. We then represent each gate by a clause giving the relationship of inputs to output. For example the clause for the following gate.

is given by    x4 ⇔ ( x1 ∧ x2 ∧ x3 ).

•       We then construct the Boolean formula by simply AND'ing all the clauses with the output (which can be done in polynomial time). Clearly both the circuit Satisfiability and Boolean Satisfiability counterparts have the same resulting decision outputs. For example, the circuit given by Φ           

                      = x10 Ù (x4 « Øx3)

          = x10 Ù (x5 « (x1 Ú x2))

 = x10 Ù (x6« Øx4)

 = x10 Ù (x7 «( x1 Ù x2 Ù x4))

 = x10 Ù (x8 « (x5 Ú x6))

 = x10 Ù (x9 « (x6 Ú x7))

 = x10 Ù (x10 « ( x7 Ù x8 Ù x9))

   •Thus if we could solve the Boolean satisfiability problem in polynomial time, we could solve the circuit satisfiability problem in polynomial time (and by extension any NP problem in polynomial time.

3-CNF Satisfiability

•Problem:

•A Boolean formula is in conjunctive normal form, or CNF, if it is an AND of clauses, each of which is an OR of literals.

•3-CNF: Each clause has exactly 3 distinct literals.

     

•Notice: true if at least one literal in each clause is true.

•Now we need to construct the reduction algorithm:

SAT  £p 3-CNF-SAT to prove NPC.

 Proof

The reduction is performed in three steps:
Step 1: Convert clauses into a binary parse tree.
–Since each Boolean operator is a binary operator, we simply construct a binary parse tree where the nodes are the operators and the literals are leaves.
–In the case of clauses with multiple literals, we simply add associative parentheses as needed to make binary clauses.
–We then construct a new expression, similarly to the above reduction from circuit Satisfiability to Boolean Satisfiability, by AND'ing the clauses representing each node with the final output.
• Step 2: Convert each clause into CNF form.
–We then construct a truth table for each clause (which contains at most 3 literals) and use the sum-of-products method to create an equivalent Boolean expression that evaluates to 0 in which we have a set of AND'ed clauses that consist of OR'ed literals (this is known as DNF form - disjunctive normal form).

–Finally we negate this expression and apply DeMorgan's law to convert this expression into the equivalent CNF form that evaluates to 1 if and only if the original expression evaluates to 1.

•Step 3: Ensure each clause has exactly 3 literals.
Finally we add auxiliary variables p and q as needed to clauses that have less than 3 literals as follows:
–If the clause contains 3 literals, then keep it as is
–If the clause contains 2 literals, then create two AND'ed clauses that contain p and ¬ p. In other words, for the clause ( xi ∨ xj ) replace it with
–
                                   ( xi ∨ xj ∨ p ) ∧ ( xi ∨ xj ∨ ¬ p )
Since for any assignment of p, one of the clauses will evaluate to the original and the other will evaluate to 1 (thus not changing the final result of the original expression).
–If the clause contains 1 literal, then create four AND'ed clauses that contain p and ¬ p and q and ¬ q. In other words, for the clause ( xi ) replace it with
                       ( xi ∨ p ∨ q ) ∧ ( xi ∨ ¬ p ∨ q ) ∧ ( xi ∨ p ∨ ¬ q ) ∧ ( xi ∨ ¬ p ∨ ¬ q )

•Again since any assignment of p and q will make one of the clauses evaluate to the original and all the others evaluate to 1.
•
•This procedure can be done in polynomial time since the first step adds at most one variable and one clause per operator in the original expression, the second step adds at most 8 clauses (since for 3 literals the truth table has 8 rows), and the third step adds at most 4 clauses.

•Thus the product of these steps remains a constant factor. Since the procedure basically applies the laws of discrete math, the final 3-CNF expression will be satisifiable if and only if the original Boolean expression is satisfiable.

•Example
Consider the Boolean expression
φ = (( x1 → x2 ) ∨ ¬ (( ¬ x1 ⇔ x3 ) ∨ x4 )) ∧ ¬ x2
–Step 1: Draw binary parse tree
Parse the expression by creating the following output variables of sub expressions:
y6 = ( ¬ x1 ⇔ x3 )
y5 = ( y6 ∨ x4 )
y4 = ( ¬ y5 )
y3 = ( x1 → x2 )
y2 = ( y3 ∨ y4 )
y1 = ( y2 ∧ ¬ x2 )

–Making each of the above operators a node gives the following parse tree.

•Thus the original expression can be rewritten (by traversing the parse tree) as
                  φ' = y1 ∧ ( y1 ⇔ ( y2 ∧ ¬ x2 ))
∧ ( y2 ⇔ ( y3 ∨ y4 ))
∧ ( y3 ⇔ ( x1 → x2 ))
∧ ( y4 ⇔ ( ¬ y5 ))
∧ ( y5 ⇔ ( y6 ∨ x4 ))

∧ ( y6 ⇔ ( ¬ x1 ⇔ x3 ))

•Step 2: Convert each clause to CNF

•Constructing the truth table for the first clause φ'1 = y1 ⇔ ( y2 ∧ ¬ x2 )) gives

•Thus we can write ¬ φ'1 by simply AND'ing the literals (negating any false values) for each row that evaluates to 0 and OR'ing all the 0 rows (i.e. sum-of-products) giving

•

¬ φ'1 = ( ¬ y1 ∧ y2 ∧ ¬ x2) ∨ ( y1 ∧ ¬ y2 ∧ ¬ x2) ∨ ( y1 ∧ ¬ y2 ∧ x2) ∨ ( y1 ∧ y2 ∧ x2)

–

•Finally we can compute the CNF form φ"1 = ¬ ( ¬ φ'1 ) and using DeMorgan's laws to convert AND to OR giving

•

φ"1 = ( y1 ∨ ¬ y2 ∨ x2) ∧ ( ¬ y1 ∨ y2 ∨ x2) ∧ ( ¬ y1 ∨ y2 ∨ ¬ x2) ∧ ( ¬ y1 ∨ ¬ y2 ∨ ¬ x2)

•For the clause φ'4 = ( y4 ⇔ ( ¬ y5 )) the truth table would be

•The sum-of-products for ¬ φ'4 gives

                     ¬ φ'4 = ( ¬ y4 ∧ ¬ y5 ) ∨ ( y4 ∧ y5 )

•The CNF form for φ"4 = ¬ ( ¬ φ'4 ) gives

                        φ"4 = ( y4 ∨ y5 ) ∧ ( ¬ y4 ∨ ¬ y5 )

•Step 3: Ensure each clause has exactly 3 literals

–Clearly all the clauses in φ"1 contain three literals, so that clause is unchanged. However for φ"4, the two clauses only contain 2 literals. Thus we add an auxiliary variable p to both of them giving

–

          φ"'4 = ( y4 ∨ y5 ∨ p ) ∧ ( y4 ∨ y5 ∨ ¬ p ) ∧ ( ¬ y4 ∨ ¬ y5 ∨ p ) ∧ (¬ y4 ∨ ¬ y5 ∨ ¬ p )

–Also note that the very first clause in φ' only contains one literal ( y1) so we expand using auxiliary variables p and q giving

–

φ"'0 = ( y1 ∨ p ∨ q ) ∧ ( y1 ∨ ¬ p ∨ q ) ∧ ( y1 ∨ p ∨ ¬ q ) ∧ ( y1 ∨ ¬ p ∨ ¬ q )

–In this manner we convert the original expression into one that contains AND'ed clauses each with exactly 3 OR'ed literals.

–Thus if we could solve 3-CNF in polynomial time we could solve general Boolean Satisfiability in polynomial time (and by extension any NP problem in polynomial time).

CLIQUE

•Problem

•A clique in an undirected graph G=(V, E) is a subset  of vertices V’ Í V, each pair of which is connected by an edge in E.

•The clique problem refers to computational problems of finding cliques (subsets of vertices, all adjacent to each other, also called complete sub graphs) in a graph.

•Three kinds of problems:

ØSearch: Find a k-clique in G 

ØDecision: Is there a k-clique in G 

ØVerification: Is this a k-clique in G

ØB,C,E,F is 4 CLIQUE.

•It can be shown that the clique problem is NP-complete by reducing 3-CNF to an instance of clique.

CLIQUE is NP-Complete

•Proof
–The proof of the reduction from 3-CNF to clique is very interesting because it takes a Boolean expression and converts it into an equivalent graph even though the problems seem to stem from different mathematical domains.
–Again the proof is constructive. Assume that the 3-CNF expression has k clauses. We then construct a graph such that if the 3-CNF expression is satisfiable, then there will be a clique on the graph of size k.
•
•Step 1: Add vertices to the graph
–For each clause, add a vertices in the graph for each literal or negated literal (since each clause has exactly 3 literals there will be 3 vertices per clause in the graph giving a total of 3k vertices in the final graph).

•Step 2: Add edges between vertices
–Add edges between vertices under the following conditions
§The two vertices come from different clauses
§The vertices are not negations of each other
–Using this procedure, it can be shown that if there is an assignment of literals for the 3-CNF formula then those literals will produce a clique of size k.
–Since at least one literal (or its negation) must be assigned 1 in the expression, these vertices will form a clique in the graph.
–Conversely, if there is a clique of size k then the clique will contain the literals that satisfy the 3-CNF formula.
–Since there are no edges between vertices from the same clause, assigning the vertices in the clique to 1 will give a satisfying assignment.

•Example
–Consider the following 3-CNF expression
φ = ( x1 ∨ ¬ x2 ∨ ¬ x3 ) ∧ ( ¬ x1 ∨ x2 ∨ x3 ) ∧ ( x1 ∨ x2 ∨ x3 )

–(clearly a satisfiable assignment is < 0/1, 0, 1>). The graph for the above expression is (with the size 3 clique shown in red).

–Note that another clique (indicated in blue) of size 3 would give the assignment <1, 1, 1> which also satisfies the 3-CNF expression.

–Thus if we could solve clique in polynomial time we could solve 3-CNF in polynomial time (and by extension any NP problem in polynomial time).

NPC Proofs

•The Sequence of Reductions: