34.4 NP-completeness proofs

A language L ⊆ {0, 1}^* is NPC if:

1. L ∈ NP and

2. L' ≤_p L, ∀ L' ∈ NP

This seems to say that we have to show that all L' ∈ NP have to be reduced to L in order to show L is in NPC. 

But this is not so:

because of transitivity, by reducing a known NP-complete Language L' to L, we implicitly reduce every language in NP to L.

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

Lemma 34.8

Given: L is a language such that L' ≤_p L for some L' ∈ NPC

• L is NP-hard.

• If L ∈ NP then L ∈ NPC.

Proof

L'' ≤_p L', ∀ L'' ∈ NP                     property 2 in NPC definition L' ∈ NPC

L is NP-hard                               By transitivity, L'' ≤_p L' ≤_p L, so L' ≤_p L, ∀ L' ∈ NP.
                                                 Satisfies property 2 of NPC.

L ∈ NPC                                     If L ∈ NP then satisfies property 1 of NPC definition.

Means that by reducing a known NP-complete language L' to L, we implicitly can reduce every language in NP 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

   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 Boolean expressions to wire connections and gates.

  φ = 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

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.