Chapter 343NPCompleteness and Reducibility 
Document last modified: 
Overview
NPcomplete class has property that if any NPcomplete problem can be solved in polynomial time, every NP problem can be solved in polynomial time.
Language HAMCYCLE_{L} is NPcomplete. If we could decide HAMCYCLE_{L} in polynomial time then we could decide every NP in polynomial time.
We know that P  NP, an answer from a polynomial time algorithm can be verified in polynomial time.
The question is whether P=NP or P≠NP.
Most computer scientists believe the relationship between NP, NPC and P at right.
satisfiable  an instance exists to which a decision problem produces a 1 output
Reducibility  tool for proving languages belong to class P

Example A_{1} decides Hamiltonian cycle visits each vertex exactly once.
L_{1 }language of Hamiltonian cycle instances.
Example: A_{1}( G )
A_{2} decides kcycle is a cycle of length exactly k unique vertices.
L_{2 }language of exactly k unique vertices cycle length instances.
Example: A_{2}( G, 5 )
For a graph with v vertices:
we can answer the question: does a Hamiltonian cycle exist?
with the question: does a cycle of length v exist?
The answer to both questions is the same.
Question
 What is x?
 What is L_{2}?
 What is A_{1}(x)?_{ }
 What is f(x)?
 What is A_{2}( f(x) )?
 What is the work of the reduction algorithm F in this case?
 L_{1} ≤_{p }L_{2}?
 L_{2} ≤_{p }L_{1}?
V= {1,2,3,4,5}
E = {(1,2),(2,1),(1,5),(5,1),...}
G = (V, E)
Lemma 34.3
If L_{1}, L_{2} ⊆ {0, 1}^{*} are languages such that L_{1} ≤_{p }L_{2 }then L_{2 } ∈ P implies L_{1 } ∈ P.
Question: What does the lemma imply about L_{1} if L_{1} ≤_{p }L_{2}?
We can think of ≤_{p }as meaning L_{1} is no worse than_{ }L_{2}
NPcompleteness
Language L ⊆ {0, 1}^{*} is NPcomplete if:
 L_{ } ∈ NP
 L' ≤_{p }L_{ }for every L'_{ } ∈ NP (meaning L' is polynomial time reducible to L)
NPhard  Language L that satisfies property 2 only (satisfying property 1 means L is polynomial time verifiable, NPhard means it is not polynomial time verifiable).
Now to prove that NPcomplete class has property that if any NPcomplete problem can be solved in polynomial time, every NP problem can be solved in polynomial time.
Theorem 34.4
Equivalent statements:
 If any NPcomplete problem is polynomial time solvable, then P=NP (all NP problems can be solved in polynomial time).
 If any NP problem is not polynomial time solvable, then no NPcomplete problem is polynomial time solvable .
Proof
Let L_{ } ∈ P and also that L_{ } ∈ NPC (the class of NPcomplete languages).
For any L'_{ } ∈ NP, by property 2 of NP definition, L' ≤_{p }L.
By Lemma 34.3, have L'_{ } ∈ P, proving the first statement.
The second statement is the contrapositive of the first (i.e. the contrapositive of p → q is ~q→ ~p).
Circuit satisfiability
Reduction relies on having a known NPcomplete problem to prove a different problem NPcomplete.
Need to prove a first problem NPcomplete.

Figure 34.7 from Cormen 

Figure 34.8 (a) and (b) from Cormen


CIRCUITSAT = {<C>: C is a satisfiable Boolean combinational circuit}
CIRCUITSAT is a language
C is a circuit
<C> is a binary string
Encoding is directed graphlike:
# of combinational elements (AND, OR and NOT gates) as with vertices
# of wires as with edges
Show that CIRCUITSAT satisfies definition of NPcomplete:
 CIRCUITSAT_{ } ∈ NP
 L' ≤_{p }CIRCUITSAT, ∀ L' ∈ NP
Lemma 34.5 The circuitsatisfiability (CIRCUITSAT) problem belongs to the class NP.
CIRCUITSAT_{ } ∈ NP
Proof:
Will provide a 2input polynomial time algorithm A that can verify CIRCUITSAT. Note that A simulates the circuit.
Inputs to A:
 standard encoding of Boolean combinational circuit C
 certificate corresponding to assignment of Boolean values to the wires in C, the inputs and outputs of each logic gate
Algorithm A constructed as:
 For each logic gate in circuit, A checks that certificate value and gate output are equal for inputs on the logic gate.
 If the circuit output is 1, A outputs a 1, otherwise A outputs a 0.
Input to A must always include the circuit C and a certificate of polynomial length in size of C, for which A outputs a 1.
Because A simulates the circuit and verifies against the certificate, A cannot be fooled by an unsatisfiable circuit no matter the certificate.
CIRCUITSAT can be verified in polynomial time and CIRCUITSAT_{ } ∈ NP
Lemma 34.6 The circuitsatisfiability problem is NPhard.
L' ≤_{p }CIRCUITSAT, ∀ L' ∈ NP (meaning L' is polynomial time reducible to CIRCUITSAT)
Proof: See text.
NPcompleteness of circuitsatisfiability relies on direct proof that L ≤_{p }CIRCUITSAT_{ }for every language L_{ } ∈ NP.
CIRCUITSAT provides the known NPcomplete problem to prove a different problem NPcomplete.