34 NP-Completeness

Nondeterministic algorithm

Nondeterministic algorithms have two phases:

1. Nondeterministic guessing (think of as some random process) phase, each time the algorithm is run the resulting guess may differ.
    
2. Deterministic verification phase, checks that the guess is a solution, returning true or false, or looping infinitely.

Example: Nondeterministic graph coloring

Use 4 colors to color 5 vertices with all adjacent vertices a different color.

Guesses (vertex order 1-5):

• RRRRR        false    All vertices Red
• RYBRG        false    Adjacent vertices 1 and 4 Red
• RBYGO        false    Too many colors (5) used
• RGRBY        true     Valid 4-coloring

Verifying

Given assignments to x₁, x₂, and x₃, verification can easily be done in O(n^k) or polynomial time.

if ((^¬x₃∧ x₁∧ x₂)∨^¬¬x₃)∧ ((x₁∨x₂)∧^¬¬x₃)∧ (^¬x₃∧ x₁∧ x₂) then print 1 else print 0

In (b) there are 3 variables and 15 operations, verification requires at most 15 operations or less than 3³ = 27.

Solving is O(2ⁿ) since may need to guess every possible input.

NP-completeness and the class P and NP

class P - Polynomial or O(n^k) for k a constant

Consists of those problems that are solvable in polynomial time by a deterministic algorithm.

Its worst case efficiency is O(p(n)) where p(n) is a polynomial.

Note that for O notation, problems solvable in logarithmic or linear time are polynomial.

Example: O(n²) sort.

class NP - Nondeterministic Polynomial

Consists of those problems that are verifiable in polynomial time.

If given a solution, could verify the solution is correct in time polynomial based on the size of the input to the problem.

Example: We just demonstrated graph coloring can be verified correct in polynomial time.

Example: Hamiltonian Cycle Problem - Find a cycle in a graph visiting each vertex exactly once.

Example at right: 2 → 3 → 4 → 5 → 1

Given: an undirected graph G = (V, E)

Certificate would be a sequence of all |V| vertices <v₁, v₂, ..., v_|V|>

To verify:

• check that each edge in the sequence (v_i, v_i+1) ∈ E(G), ∀ i: 1 ≤ i ≤ |V| - 1
• and the edge (v_|V|, v₁) ∈ E(G).

Verification can be done in polynomial time, Ω(|V|)

P | NP

class NPC - NP Complete

Consists of problems in NP and are as hard as any problem in NP

If any problem in NPC can be solved in polynomial time, then all problems in NPC can be solved in polynomial time.

Abstract Problems

Example

A Path problem instance is the input: a triple (G, u, v), where G is a directed graph and u and v are vertices in the graph.

At right: G =( V, E ), u=s, v=x.

 

Path's I - is the set of all problem instances of the Path type. 

I = {i₁, i₂, ... }, where each i_j is of the form (G, u, v).

(G, s, x) represents one instance of I.

 

Path's S - is the set of all Path solutions.  S = {s₁, s₂, ... }, where each s_j is of the form <v₁, v₂,  ..., s_n >, a sequence of vertices in the graph, or <|> if no path exists.

For the graph, one instance of S is the path <s, y, z, x>

For the graph, one instance not of S is the path <x, s>

 

The Path Abstract Problem (PAP):

• Is a relation PAP | I x S such that members of the relation are tuples of the form (i_j, s_k) and appear in the relation only when solution s_k is a solution to problem instance i_j.

  Example: i_j=(G, s, x), s_k=<s, y, z, x> so (i_j, s_k) ∈ PAP, that is an (instance, solution) tuple.
   

• (i_j, s_k) does not appear in PAP if s_k is not a solution to problem instance i_j 
   
•  i_j may appear in PAP more than once since there may be more than one solution to problem instance i_j

Example

The Path abstract decision problem is a four-tuple (G, u, v, k), where G is a graph and u and v are vertices in the graph, and k is the upper limit on the number of edges in the path from u to v.

Path's I - is the set of all problem instances of the Path type.  I = {i₁, i₂, ... }, where each i_j is of the form (G, u, v, k) 

Path's S - is the set of all Path solutions.  S = {0, 1}

The Path Abstract Decision Problem (PADP):

• Is a relation PADP | I X S such that

  members of the relation are tuples of the form (i_j, s_k) and ∀j i_j ∈ I then (i_j, 0) ∈ PADP or (i_j, 1) ∈ PADP,

  where s_k = 0 if there does not exist a path from u to v of at most k edges

  and s_k = 1 if a path does exists with at most k edges.

  Examples

  i_j = (G, s, z, 20), s_k=1

  i_j = (G, s, z, 1), s_k=0

Summary

To develop a method for showing a problem is NP-complete, we need a general representation of problems (abstract) and that have a yes/no answer (decision).

 

Algorithms that verify membership in a language

x - a problem instance (input string)

y - a certificate (solution string)

A - an algorithm, verifies x if there exists a certificate y such that A(x, y) = 1

Language verified by A is:

L = {x ∈ {0, 1}^* : ∃ certificate y ∈ {0, 1}^* such that A(x, y) = 1}

{0, 1}^* is a binary encoding, e.g. 10000001₂ = 'A'

Algorithm A verifies language L if for any string x ∈ L, there is a certificate y that A can use to prove that x ∈ L.

For any string, x ⊆ L, there is no certificate proving that x ∈ L.

 

Example: Hamiltonian graph cycle (HAM-CYCLE) is a simple cycle that contains each vertex.

The certificate is the list of vertices in the Hamiltonian graph cycle, enough information for verification

(e.g. vertices <1, 2, 3, 4, 5>)

If not Hamiltonian, there is no list that can fool the verification algorithm.

Algorithm A would not be fooled by <2, 1, 3, 4, 5>

L is just those input strings of vertices which are a Hamiltonian cycle.

{<1, 2, 3, 4, 5>, <2, 3, 4, 5, 1>, ..., <5, 4, 3, 2, 1>, ...}

Example:

For one instance of HAM-CYCLE_L where:

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

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

G = (V,  E)

A_HAM-CYCLE( G, <1, 2, 3, 4, 5>) = 1

A_HAM-CYCLE( G, <1, 2>)  ¹ 1

 

Complexity class NP - Nondeterministic Polynomial time

A class of languages that can be verified by a polynomial-time algorithm.

L ∈ NP iff ∃ a 2-input polynomial-time algorithm A and constant c such that:

L = {x ∈ {0, 1}^* : ∃ a certificate y with |y| = O( |x|^c ) such that A(x, y) = 1}

The upper bound of the solution length, |y|, is polynomial

x is the instance (input) and y is the solution to be verified

Algorithm A verifies L in polynomial time

Example: Proving PATHL ∈ NP PATH problem: xi = (G, u, v, k), where G is the graph, u is the source vertex, v is the target vertex, k is an integer specifying the maximum allowable length of a path from u to v. Given PATH problem instance: x1 = (G, r, y, 5), certificate p = < r, s, w, x, y > use APATH (x1, p) to verify that path p's length is ≤ k APATH (x, p) verifies p is a path in x's G of length k or less in polynomial time by: APATH(x, p) verifies PATHL as follows: Verify x is a proper encoding of <G, u, v, k> Verify each v ∈ p is unique, i.e. p is a set. Verifies first vertex in list is: u ∈ x. Verifies last vertex in list is: v ∈ x. Verify length[p] ≤ k for i ← 1 to length[p]-1 do verify (vi, vi+1) ∈ G.E If steps 1-6 verify, APATH (x, p) = 1 Therefore PATHL ∈ NP, since APATH(x, p) can produce either a 0 or a 1 in polynomial time. But we already knew that PATH ∈ P, and P ∈ NP, i.e., anything that can be computed in polynomial time can be verified in polynomial time.

 

NP-completeness

Language L ⊆ {0, 1}* is NP-complete if: L ∈ NP      (meaning L is polynomial time verifiable)   L' ≤p L for every L' ∈ NP  (meaning all L' are 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).

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).

A First NP-Complete problem

NP-hard

A language L that satisfies L' ≤_p L, ∀ L' ∈ NP (means every language in NP can be reduced in polynomial time to L).

Example - Prove Formula satisfiability is NPC

SAT = { <φ>: φ is an instance of a Boolean formula}

φ is composed of:

• n Boolean variables: x₁, x₂, ..., x_n

• m Boolean connectives: ^, v, ¬, → , ↔

• ( ) parenthesis

Example Formula: φ = ((x₁ → x₂) v ¬((¬x₁ ↔ x₃) v x₄)) ^ ¬x₂

n = 4, m = 8

• φ ∈ SAT if φ has a satisfying assignment to x_i

• For the formula above try: x₁ = 0, x₂ = 0, x₃ = 1, x₄ = 1

• There are 2ⁿ possible assignments to φ

• Checking all requires at least Ω(2ⁿ) time

Overall Steps for Showing SAT ∈ NPC

1. Show SAT ∈ NP

   A_SAT(φ, y) = 1            Verify certificate y as solution to φ

   A_SAT runs in polynomial time by just replacing each x_i with its corresponding value from y and evaluating expression. Simulate φ to verify certificate.

2. Show CIRCUIT-SAT ≤_p SAT

   1. Select a known NPC language L' (i.e. choose CIRCUIT-SAT)
       

   2. Describe an algorithm F that computes a function f, mapping every instance of x ∈ {0, 1}^* of CIRCUIT-SAT to an instance f(x) ∈ SAT

      See below.

   3. Prove that the function f satisfies: x ∈ CIRCUIT-SAT iff  f(x) ∈ SAT, ∀ x ∈ {0, 1}^*
       

   4. Prove that F computes f in polynomial time

CIRCUIT-SAT ≤_p SAT has been shown.

 

SAT ∈ NP and CIRCUIT-SAT ≤p SAT Hence SAT ∈ NPC

By Lemma 34.8, if L is a language such that L' ≤_p L for some L' ∈ NPC, then L is NP-hard. Also, if L ∈ NP then L ∈ NPC.

That is: if SAT is a language such that CIRCUIT-SAT ≤_p SAT for CIRCUIT-SAT ∈ NPC, then SAT is NP-hard. Also, if SAT ∈ NP then SAT ∈ NPC.

 

• F reduces CIRCUIT-SAT instance to SAT instance by converting wire connections and gates to Boolean expressions.

  φ = x₁₀ ^ (x₄ ↔ ¬x₃)
              ^ (x₅ ↔ (x₁ v x₂))
              ^ (x₆ ↔ ¬x₄)
              ^ (x₇ ↔ (x₁ ^ x₂ ^ x₄))
              ^ (x₈ ↔ (x₅ v x₆))
              ^ (x9 ↔ (x₆ v x₇))
              ^ (x₁₀ ↔ (x₇ ^ x₈ ^ x9)

   

• For this circuit to be satisfiable, there has to be a satisfying assignment to x₁ .. x₁₀

• Satisfied by: x₁ = 1, x₂ = 1, x₃ = 0, x₄ = 1, x₅ = 1, x₆ = 0, x₇ = 1, x₈ = 1, x9 = 1, x₁₀ = 1 

What This Reduction Shows - CIRCUIT-SAT ≤_p SAT

Already shown SAT ∈ NP Reduction shows CIRCUIT-SAT ≤p SAT Hence SAT ∈ NPC

So we can construct a machine as follows: A1 is CIRCUIT-SAT ∈ NPC A2 is SAT F is the polynomial-time reduction algorithm that computes the function f x is a problem instance of CIRCUIT-SAT f(x) is a problem instance of SAT

Figure 34.5 from Cormen

• If a polynomial-time algorithm existed for SAT (i.e., A₂  in the diagram), then we could construct a machine similar to Figure 34.5 that could decide A₁ in polynomial time.
   

• But we know that no known polynomial-time algorithm has ever been discovered for CIRCUIT-SAT (i.e., A₁ in the diagram)
   

• Therefore, by contradiction, it is not likely that a polynomial-time algorithm exists for SAT
   

• A proof that a problem is NP-complete is excellent evidence it is intractable.