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 (Cooks 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
Reviews
There are no reviews yet.