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 (ab), (ab)
a
b c
a=bc clauses (ab), (ac), (abc)
a
b c
a=bc clauses (ab), (ac), (abc)
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 (r1r2) by two clauses
(r1r2 p), (r1r2 p), where p is a new variable (or any
other variable of ’)
– Replace the 1-literal clause z by 4 clauses (zpq),
(zpq), (zpq), (zpq)
• 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=(abc) 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