# 程序代写代做代考 algorithm Microsoft PowerPoint – lecture13 [Compatibility Mode]

Microsoft PowerPoint – lecture13 [Compatibility Mode]

COMS4236: Introduction to
Computational Complexity

Spring 2018

Mihalis Yannakakis

Lecture 13, 2/27/18

Proving a problem B is NP-complete
• Show the problem B is in NP
• Show B is NP-hard
1. Pick a problem A that you know is NP-hard, preferably a

problem close to B
2. Find an algorithm f that maps instances of A to instances

of B
3. Prove that if x is a Yes instance of A then f(x) is a Yes

instance of B
4. Conversely, prove that if f(x) is a Yes instance of B then x

is a Yes instance of A (equivalently, if x is a No instance of
A then f(x) is a No instance of B )

5. Prove that f runs in polynomial time (or log-space)

* If B is not a decision problem, formulate the corresponding
decision problem (NP is a class of decision problems)

Boolean Formula Satisfiability
• Special case of Circuit-SAT
• Boolean Formula with operators , ,  equivalent to

circuit that is a tree, the parse tree of the formula



x y z

( ( x  y)  (y) )  (x  z)  ( (y  z) )

zyy x

CNF Satisfiability
• Boolean formula is in Conjunctive Normal Form (CNF) if

it is the AND of clauses where a clause is the OR of
literals. A literal is a variable or its negation.
( x  y)  (x  y  z)  (x  y  z)  ( y  z )

Clauses

Disjunctive Normal Form (DNF): OR of ANDs of literals

Every Boolean function has an equivalent CNF (and DNF)
formula, but the conversion from a circuit or formula to a CNF
or DNF formula may incur an exponential blowup in size.

– Not a polynomial time reduction

CNF formula satisfiable   truth assignment to the
variables that satisfies all the clauses

3SAT is NP-complete (Cook’s Theorem)
• 3SAT = Satisfiability of a CNF Boolean formula with 3

literals in each clause (a 3CNF formula).
• 3SAT in NP: “guess” a satisfying truth assignment (the

certificate) and check that it satisfies all the clauses
• 3SAT is NP-hard:
• Reduction from Fan-in 2 CIRCUIT-SAT.
Given circuit C with fan-in 2, will construct in polynomial

time a 3CNF formula  such that C is satisfiable iff  is
satisfiable.

From CIRCUIT-SAT to 3SAT ctd.
1. Introduce a variable for every input and gate of the circuit.
2. Include a set of clauses for each gate stating that the truth

value of the corresponding gate variable is the
NOT/AND/OR of the values of its input variables

a

b

a= b  conjunction of clauses (ab), (ab)

a

b c

a=bc  clauses (ab), (ac), (abc)

a

b c

a=bc  clauses (ab), (ac), (abc)

3. Let ’ = conjunction of all the gate clauses and an
additional unit clause z, where z is the variable
corresponding to the output gate.

’ is a CNF formula with at most 3 literals per clause, and

’ is satisfiable iff the circuit C’ is satisfiable.

From CIRCUIT-SAT to 3SAT ctd.

Example

 

x y z Inputs

Output

Gates

Example

 

x y z

a c

d e

b

g

f

h

Example

 

x y z

a c

d e

b

g

f

h ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( ) ( )

h
h g h f h g f
g d g e g d e
f z f z
e b e c e b c
d a d b d a b
c y c z c y z
b y b y
a x a y a x y

      

      

   

      

      
      

   
     

’ is a CNF formula with at most 3 literals per clause, and
’ is satisfiable iff the circuit C’ is satisfiable.

4. Transform ’ to a 3CNF formula  with exactly 3 literals
per clause:

– Replace each 2-literal clause (r1r2) by two clauses
(r1r2 p), (r1r2 p), where p is a new variable (or any
other variable of ’)

– Replace the 1-literal clause z by 4 clauses (zpq),
(zpq), (zpq), (zpq)

• The resulting 3CNF formula  is satisfiable iff the circuit
C is satisfiable.

• can be constructed from C in log space (and
polynomial time)

From CIRCUIT-SAT to 3SAT ctd.

Not-All-Equal 3SAT (NAE3SAT)
• NAE clause: Set of literals. Clause is satisfied by a truth

assignment iff not all literals have the same truth value.

• NAE3SAT
• Input: Set of NAE clauses with 3 literals in each clause
• Question:  assignment that satisfies all the clauses?

• NAE3SAT is NP-complete
• in NP: Guess a satisfying assignment
• NP-hard: Reduction from 3SAT

3SAT ≤log NAE3SAT
• 3SAT clause Ci=(abc)  NAE clauses (a,b,yi), (yi,c,0)
where yi is a new variable corresponding to Ci
• If a truth assignment sets a=b=c=0, then the NAE clauses

become (0,0,yi), (yi,0,0) and cannot be satisfied no matter
what we set yi

• Conversely, if at least one of a,b,c is 1, then we can set yi
to satisfy both clauses (if a or b =1 then set yi=0, else 1).

 The given set of 3SAT clauses has a satisfying truth
assignment iff the constructed set of NAE3SAT clauses
has a satisfying truth assignment

3SAT ≤log NAE3SAT ctd.
• The constructed NAE3SAT clauses contain the constant 0
• NAE3SAT is NP-complete even if we disallow constants

• Replace all occurrences of 0 by a new variable z.
• Since no constants, a truth assignment satisfies all

NAE3SAT clauses iff the complementary assignment (flip
all truth values) satisfies the clauses.

 The new set of NAE3SAT clauses has a satisfying
assignment iff it has one that sets z=0, which is the case iff
the given set of 3SAT clauses has a satisfying assignment.

• 2SAT and NAE2SAT are in P