Introduction

Proving that a problem is NP-complete is a fundamental skill in computational complexity theory. The standard approach is to reduce from a known NP-complete problem (like 3-SAT) to the problem we want to prove is NP-complete. This post provides a systematic guide with detailed examples of how to construct and verify such reductions.

Understanding NP-Completeness Proofs

The Two-Step Process

To prove that a problem X is NP-complete, we need to show two things:

  1. X ∈ NP: The problem is in NP (solutions can be verified in polynomial time)
  2. Y ≤ₚ X: Some known NP-complete problem Y reduces to X in polynomial time

If both conditions hold, then X is NP-complete.

Why This Works

  • If Y ≤ₚ X and Y is NP-complete, then X is at least as hard as Y
  • Since Y is NP-complete (hardest problems in NP), X must also be NP-complete
  • The reduction shows that if we could solve X efficiently, we could solve Y efficiently

The Standard Starting Point: 3-SAT

3-SAT (3-CNF Satisfiability) is the most commonly used starting point for reductions because:

  1. It’s the first problem proven NP-complete (Cook-Levin Theorem)
  2. It’s conceptually simple (Boolean logic)
  3. Many problems naturally encode logical constraints

3-SAT Problem:

  • Input: A Boolean formula φ in 3-CNF (conjunctive normal form with exactly 3 literals per clause)
  • Output: YES if φ is satisfiable, NO otherwise

Example: φ = (x₁ ∨ !x₂ ∨ x₃) ∧ (!x₁ ∨ x₂ ∨ x₃) ∧ (x₁ ∨ x₂ ∨ !x₃)

General Strategy for Reductions

Step-by-Step Process

  1. Understand the target problem: Clearly define what you’re trying to prove NP-complete
  2. Design the reduction: Create a polynomial-time transformation from 3-SAT instances to instances of your problem
  3. Prove correctness: Show that 3-SAT instance is satisfiable ↔ your problem instance has a solution
  4. Verify polynomial time: Ensure the transformation takes polynomial time

Key Components of a Reduction

Gadgets: Small structures that encode parts of the 3-SAT instance

  • Variable gadgets: Encode variable assignments
  • Clause gadgets: Encode clause satisfaction
  • Connections: Link gadgets to ensure consistency

Example 1: Reducing 3-SAT to Independent Set

Problem: Independent Set

Input: Graph G = (V, E) and integer k Output: YES if G has an independent set of size ≥ k, NO otherwise

Reduction Construction

Step 1: Create Variable Gadgets

  • For each variable xᵢ in the 3-SAT formula, create two vertices: vᵢ (representing xᵢ = TRUE) and v’ᵢ (representing xᵢ = FALSE)
  • Connect vᵢ and v’ᵢ with an edge (ensures we can’t pick both)

Step 2: Create Clause Gadgets

  • For each clause Cⱼ = (l₁ ∨ l₂ ∨ l₃), create a triangle (3 vertices connected in a cycle)
  • Label vertices: cⱼ,₁, cⱼ,₂, cⱼ,₃ corresponding to literals l₁, l₂, l₃

Step 3: Connect Clause to Variable Gadgets

  • For each clause vertex cⱼ,ᵢ representing literal l:
    • If l = xₖ, connect cⱼ,ᵢ to vₖ (if xₖ = FALSE, we can’t use this clause vertex)
    • If l = !xₖ, connect cⱼ,ᵢ to v’ₖ (if xₖ = TRUE, we can’t use this clause vertex)

Step 4: Set k = n + m

  • n = number of variables (one from each variable pair)
  • m = number of clauses (one from each clause triangle)

Correctness Proof

Forward Direction (3-SAT satisfiable → Independent Set exists):

  • If φ is satisfiable, pick vertices:
    • For each variable xᵢ: pick vᵢ if xᵢ = TRUE, else pick v’ᵢ
    • For each clause Cⱼ: pick the clause vertex corresponding to a true literal
  • This gives an independent set of size n + m:
    • Variable vertices don’t conflict (we pick one per pair)
    • Clause vertices don’t conflict (triangle edges prevent picking two from same clause)
    • Clause vertices don’t conflict with variable vertices (by construction, if literal is true, the connection prevents conflict)

Reverse Direction (Independent Set exists → 3-SAT satisfiable):

  • If independent set of size n + m exists:
    • Must pick exactly one vertex from each variable pair (n vertices)
    • Must pick exactly one vertex from each clause triangle (m vertices)
  • Set xᵢ = TRUE if vᵢ is picked, else xᵢ = FALSE
  • Each clause has at least one true literal (the clause vertex picked corresponds to a true literal)

Polynomial Time:

  • Creating graph: O(n + m) vertices, O(n + 3m + 3m) edges = O(n + m)
  • Total: O(n + m) time

Therefore, Independent Set is NP-complete.

Example 2: Reducing 3-SAT to Vertex Cover

Problem: Vertex Cover

Input: Graph G = (V, E) and integer k Output: YES if G has a vertex cover of size ≤ k, NO otherwise

Reduction Construction

Key Insight: Use the complement relationship with Independent Set

  • S is an independent set ↔ V \ S is a vertex cover
  • Independent set of size ≥ k ↔ Vertex cover of size ≤ n - k

Reduction:

  1. Reduce 3-SAT to Independent Set (as above) to get graph G and k = n + m
  2. Return Vertex Cover instance: graph G, k’ = n - (n + m)

Correctness:

  • 3-SAT satisfiable ↔ Independent set of size n + m exists ↔ Vertex cover of size n - (n + m) exists

Polynomial Time: O(n + m)

Therefore, Vertex Cover is NP-complete.

Example 3: Reducing 3-SAT to Clique

Problem: Clique

Input: Graph G = (V, E) and integer k Output: YES if G has a clique of size ≥ k, NO otherwise

Reduction Construction

Key Insight: Use complement graph relationship

  • S is a clique in G ↔ S is an independent set in G̅ (complement graph)

Reduction:

  1. Reduce 3-SAT to Independent Set to get graph G and k = n + m
  2. Create complement graph G̅
  3. Return Clique instance: graph G̅, k = n + m

Correctness:

  • 3-SAT satisfiable ↔ Independent set of size n + m in G ↔ Clique of size n + m in G̅

Polynomial Time: O(n²) to create complement graph

Therefore, Clique is NP-complete.

Example 4: Reducing 3-SAT to 3D Matching

Problem: 3D Matching

Input: Sets X, Y, Z and set T ⊆ X × Y × Z of triples Output: YES if there exists a matching M ⊆ T covering all elements, NO otherwise

Reduction Construction

Step 1: Variable Gadgets

  • For each variable xᵢ, create 2m elements in each of X, Y, Z (where m = number of clauses)
  • Create triples connecting these elements in a chain

Step 2: Clause Gadgets

  • For each clause Cⱼ, create elements that can be matched if clause is satisfied
  • Connect to variable gadgets based on which literals appear

Step 3: Consistency

  • Ensure matching covers all elements
  • Ensure variable assignments are consistent across clauses

Detailed Construction:

  • For variable xᵢ and clause Cⱼ:
    • If xᵢ appears positively in Cⱼ: create triple allowing TRUE assignment
    • If !xᵢ appears in Cⱼ: create triple allowing FALSE assignment
  • Matching exists ↔ each variable has consistent assignment ↔ each clause is satisfied

Polynomial Time: O(nm) triples created

Therefore, 3D Matching is NP-complete.

Example 5: Reducing 3-SAT to Subset Sum

Problem: Subset Sum

Input: Set S of integers and target t Output: YES if there exists subset S’ ⊆ S with sum exactly t, NO otherwise

Reduction Construction

Key Idea: Use numbers in base representation to encode constraints

Step 1: Number Representation

  • Use numbers with digits corresponding to variables and clauses
  • Each number has n + m digits (n variables + m clauses)

Step 2: Variable Numbers

  • For each variable xᵢ, create two numbers:
    • Number for xᵢ = TRUE: digit i = 1, other variable digits = 0
    • Number for xᵢ = FALSE: digit i = 1, other variable digits = 0
  • Both have clause digits based on which clauses they satisfy

Step 3: Clause Numbers

  • For each clause Cⱼ, create numbers to ensure at least one literal is true
  • Use “slack” numbers to allow flexibility

Step 4: Target

  • Target t has all variable digits = 1 (each variable assigned)
  • All clause digits = 1 (each clause satisfied)

Example (simplified):

  • Variables: x₁, x₂
  • Clauses: (x₁ ∨ x₂), (!x₁ ∨ x₂)
  • Create numbers encoding assignments and clause satisfaction
  • Target: 1111 (both variables assigned, both clauses satisfied)

Polynomial Time: O(nm) numbers, each with O(n + m) digits

Therefore, Subset Sum is NP-complete.

Common Reduction Patterns

Pattern 1: Graph Problems from 3-SAT

Many graph problems use similar gadgets:

  • Variable gadgets: Two vertices (TRUE/FALSE) connected by edge
  • Clause gadgets: Structures requiring at least one element
  • Consistency edges: Connect gadgets to enforce constraints

Examples: Independent Set, Vertex Cover, Clique, Dominating Set

Pattern 2: Set Problems from 3-SAT

Set problems often use:

  • Variable sets: Elements representing variable assignments
  • Clause sets: Elements that must be covered
  • Intersection constraints: Ensure consistency

Examples: Set Cover, Exact Cover, Hitting Set

Pattern 3: Optimization Problems from 3-SAT

Optimization problems encode:

  • Variables: Decision variables
  • Constraints: Linear or integer constraints encoding clauses
  • Objective: Often just feasibility (any solution works)

Examples: Integer Linear Programming, Zero-One Equations

Pattern 4: Using Known Reductions

Once you prove one problem NP-complete, you can reduce from it:

  • Independent Set → Clique: Use complement graph
  • Independent Set → Vertex Cover: Use complement relationship
  • Vertex Cover → Set Cover: Encode edges as sets

Step-by-Step Reduction Template

Template for Proving NP-Completeness

Step 1: Show Problem ∈ NP

  • Describe verification algorithm
  • Show it runs in polynomial time

Step 2: Choose Known NP-Complete Problem

  • Usually 3-SAT or a closely related problem

Step 3: Design Reduction

  • Describe transformation from known problem to your problem
  • Show it’s polynomial time

Step 4: Prove Correctness

  • Forward: Known problem YES → Your problem YES
  • Reverse: Your problem YES → Known problem YES

Step 5: Verify Polynomial Time

  • Count vertices/edges/elements created
  • Show polynomial in input size

Tips for Constructing Reductions

1. Start Simple

  • Begin with small examples (2-3 variables, 2-3 clauses)
  • Verify your construction works manually

2. Use Gadgets

  • Break problem into smaller pieces
  • Design gadgets for variables and clauses separately
  • Connect gadgets to enforce constraints

3. Think About Constraints

  • What must be true for a solution to exist?
  • How can you encode “at least one” constraints?
  • How can you encode “exactly one” constraints?

4. Verify Both Directions

  • Don’t just show one direction
  • Both forward and reverse are crucial

5. Check Polynomial Time

  • Count what you create
  • Ensure it’s polynomial in input size
  • Don’t create exponential objects

Common Pitfalls

Pitfall 1: Only Showing One Direction

  • Must prove both: Known → Your and Your → Known
  • One direction alone doesn’t prove NP-completeness

Pitfall 2: Exponential Reduction

  • Reduction must be polynomial time
  • Creating 2ⁿ objects makes reduction exponential

Pitfall 3: Incorrect Gadget Design

  • Gadgets must correctly encode constraints
  • Test on small examples first

Pitfall 4: Forgetting to Show ∈ NP

  • Must show problem is in NP first
  • Otherwise it could be harder than NP

Practice Problems

  1. Reduce 3-SAT to Hamiltonian Cycle: Design gadgets for variables and clauses. How do you ensure a cycle visits all vertices?

  2. Reduce 3-SAT to Set Cover: Encode variables and clauses as sets. What should the universe be?

  3. Reduce Vertex Cover to Dominating Set: Use the relationship between vertex covers and dominating sets.

  4. Reduce 3-SAT to Partition: Encode variable assignments and clause satisfaction using subset sums.

  5. Reduce Independent Set to Maximum Cut: Show how independent sets relate to cuts in graphs.

  6. Reduce 3-SAT to Graph Coloring: Encode variable assignments as colors. How many colors do you need?

  7. Prove your own reduction: Pick a problem and reduce from 3-SAT. Write out the full proof.

  8. Chain reductions: Reduce 3-SAT → Problem A → Problem B. What does this tell you about Problem B?

Key Takeaways

  1. Two-step process: Show ∈ NP and reduce from known NP-complete problem
  2. 3-SAT is standard: Most reductions start from 3-SAT
  3. Gadgets are key: Design variable and clause gadgets carefully
  4. Prove both directions: Forward and reverse correctness are essential
  5. Polynomial time: Reduction must be efficient
  6. Practice helps: Work through examples to develop intuition

Reduction Summary

3-SAT ≤ₚ Independent Set:

  • Variable gadgets: pairs of vertices
  • Clause gadgets: triangles
  • k = n + m

3-SAT ≤ₚ Vertex Cover:

  • Via Independent Set complement relationship
  • k = n - (n + m)

3-SAT ≤ₚ Clique:

  • Via complement graph of Independent Set
  • k = n + m

3-SAT ≤ₚ 3D Matching:

  • Variable gadgets: chains of triples
  • Clause gadgets: triples for clause satisfaction
  • Matching covers all elements

3-SAT ≤ₚ Subset Sum:

  • Base representation encoding
  • Variable digits and clause digits
  • Target has all 1s

All reductions are polynomial-time, establishing these problems as NP-complete.

Further Reading

  • Garey & Johnson: “Computers and Intractability” - Comprehensive catalog of NP-complete problems and reductions
  • Cook-Levin Theorem: Original proof that SAT is NP-complete
  • Karp’s 21 Problems: Original set of NP-complete problems and their reductions
  • Reduction Techniques: Advanced techniques like local replacement, component design, and restriction

Understanding how to construct reductions is essential for proving NP-completeness. The key is to design gadgets that correctly encode the constraints of the known NP-complete problem (like 3-SAT) into the structure of your target problem. With practice, you’ll develop intuition for which reduction techniques work best for different problem types.