Chapter 34-3

NP-Completeness and Reducibility
Document last modified: 

Overview

NP-complete class has property that if any NP-complete problem can be solved in polynomial time, every NP problem can be solved in polynomial time.

Language HAM-CYCLEL is NP-complete. If we could decide HAM-CYCLEL 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

Problem Q can be reduced to problem Q' if any instance of Q can be easily rephrased (i.e. polynomial time) as an instance of Q'. The solution to Q' provides a solution to Q.

L1 ≤p L2

Language L1 is polynomial time reducible to language L2 if there exists a polynomial time function:

f : {0, 1}* → {0, 1}* such that for all x ∈ {0, 1}*

x ∈ {0, 1}* iff f(x) ∈ L2

f is the reduction function, converting an instance of A1 to an instance of  A2.

F is the reduction algorithm, the polynomial time algorithm that computes f.

For decision problem represented by L1

for any x ∈ L1, f(x) ∈ L2

 F computes reduction function f.

A2 decides L2 in polynomial time.

A1 algorithm decides x ∈ L1 using F to transform x into f(x), then using A2 to decide if f(x) ∈ L2.

If f(x) ∈ L2 then x ∈ L1.

 
Example

A1 decides Hamiltonian cycle visits each vertex exactly once.

L1 language of Hamiltonian cycle instances.

Example: A1( G )

A2 decides k-cycle is a cycle of length exactly k unique vertices.

L2 language of exactly k unique vertices cycle length instances.

Example: A2( 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
  1. What is x?
  2. What is L2?
  3. What is A1(x)?
  4. What is f(x)?
  5. What is A2( f(x) )?
  6. What is the work of the reduction algorithm F in this case?
  7. L1 ≤p L2?
  8. L2 ≤p L1?

V= {1,2,3,4,5}

E = {(1,2),(2,1),(1,5),(5,1),...}

G = (V,  E)

Lemma 34.3

If  L1, L2 ⊆ {0, 1}* are languages such that L1 ≤p L2 then L2 ∈ P implies  L1 ∈ P.

Question: What does the lemma imply about L1 if L1 ≤p L2?

We can think of ≤p as meaning L1 is no worse than L2

NP-completeness

Language L ⊆ {0, 1}* is NP-complete if:

  1. L ∈ NP
  2. L' ≤p L for every L' ∈ NP  (meaning L' is polynomial time reducible to L)

 

NP-hard - Language L that satisfies property 2 only (satisfying property 1 means L is polynomial time verifiable, NP-hard means it is not polynomial time verifiable).

Now to prove that NP-complete class has property that if any NP-complete problem can be solved in polynomial time, every NP problem can be solved in polynomial time.

Theorem 34.4

Equivalent statements:

  1. If any NP-complete problem is polynomial time solvable, then P=NP (all NP problems can be solved in polynomial time).
  2. If any NP problem is not polynomial time solvable, then no NP-complete problem is polynomial time solvable .

Proof

Let L ∈ P and also that L ∈ NPC (the class of NP-complete 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 NP-complete problem to prove a different problem NP-complete.

Need to prove a first problem NP-complete.

The First NP-Complete Problem

Circuit-Satisfiability - given a Boolean circuit constructed from AND, OR and NOT gates, determine whether there is any set of Boolean inputs to the circuit that causes an output of 1.

Brute force solution for n inputs requires 2n comparisons so is super-polynomial.

Circuit is satisfiable if has a satisfying assignment of Boolean values.

Figure (a) is satisfiable but (b) is not.

Figure 34.7 from Cormen

Figure 34.8 (a) and (b) from Cormen

((¬x3∧ x1∧ x2)∨¬x3)∧ ((x1∨x2)∨¬x3)∧ (¬x3∧ x1∧ x2)
x1 x2 x3 Output
0 0 0 ?
0 0 1 ?
0 1 0 ?
0 1 1 ?
1 0 0 ?
1 0 1 ?
1 1 0 1
1 1 1 ?

CIRCUIT-SAT = {<C>: C is a satisfiable Boolean combinational circuit}

CIRCUIT-SAT is a language

C is a circuit

<C> is a binary string

Encoding is directed graph-like:

# of combinational elements (AND, OR and NOT gates) as with vertices

# of wires as with edges

Show that CIRCUIT-SAT satisfies definition of NP-complete:

  1. CIRCUIT-SAT ∈ NP
  2. L' ≤p CIRCUIT-SAT, ∀ L' ∈ NP

Lemma 34.5 The circuit-satisfiability (CIRCUIT-SAT) problem belongs to the class NP.

CIRCUIT-SAT ∈ NP

Proof:

Will provide a 2-input polynomial time algorithm A that can verify CIRCUIT-SAT. Note that A simulates the circuit.

Inputs to A:

  1. standard encoding of Boolean combinational circuit C
  2. 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.

CIRCUIT-SAT can be verified in polynomial time and CIRCUIT-SAT ∈ NP

Lemma 34.6 The circuit-satisfiability problem is NP-hard.

L' ≤p CIRCUIT-SAT, ∀ L' ∈ NP  (meaning L' is polynomial time reducible to CIRCUIT-SAT)

Proof: See text.

NP-completeness of circuit-satisfiability relies on direct proof that L ≤p CIRCUIT-SAT for every language L ∈ NP.

CIRCUIT-SAT provides the known NP-complete problem to prove a different problem NP-complete.