Neural Sync Active

NP-Completeness — P, NP, NP-Hard, Reductions

Registry Synced

NP-Completeness — P, NP, NP-Hard, Reductions

1113 words

6 min read

Reading compass

Now · 🎯 Learning Objectives

NP-Completeness — P, NP, NP-Hard, Reductions

🎯 Learning Objectives

Define complexity classes P, NP, NP-hard, NP-complete
Prove a problem is NP-complete via reduction
Perform reductions between SAT, 3-SAT, Clique, Vertex Cover, Subset Sum
Explain the Cook-Levin theorem

1. Complexity Classes

1.1 Intuition

Some problems are easy (can be solved quickly), some are hard (we don't know fast algorithms). P is the set of "tractable" problems. NP is the set of problems with "easily verifiable" solutions. The P vs NP question asks: if we can quickly verify a solution, can we also quickly find one?

1.2 Formal Definitions

(Diagram)

Class	Definition	Example
P	Solvable in polynomial time $O(n^k)$	Sorting, shortest path
NP	Verifiable in polynomial time	Sudoku (verify a solution is easy)
NP-hard	Every problem in NP reduces to it	Halting problem (can be undecidable!)
NP-complete	In NP and NP-hard	SAT, 3-SAT, Clique, Vertex Cover

1.3 Key Questions

P = NP? Unknown ($1M Clay Millennium Prize)
NP = co-NP? Unknown
Is every NP-hard problem in NP? No (e.g., optimization versions)

2. Polynomial-Time Reductions

2.1 Intuition

A reduction transforms instances of problem A into instances of problem B, such that solving B solves A. If we can solve B efficiently, we can solve A efficiently.

2.2 Formal Definition

A \leq_p B

(A reduces to B in polynomial time) if there exists a polynomial-time computable function

f

such that:

x \in A \iff f(x) \in B

(Diagram)

2.3 Reduction Examples

3-SAT → Independent Set Given a 3-CNF formula, construct a graph where:

Each clause has 3 nodes (one per literal)
Connect literals in the same clause (triangle)
Connect each literal to its negation
Formula satisfiable ↔ graph has independent set of size = number of clauses Independent Set → Clique The complement graph flips edges and non-edges. An independent set in G is a clique in the complement of G.

3. Classic NP-Complete Problems

3.1 SAT (Satisfiability)

Problem: Given a Boolean formula, is there a satisfying assignment? Cook-Levin Theorem: SAT is NP-complete. Every NP problem can be reduced to SAT.

3.2 3-SAT

Problem: Given a 3-CNF formula (AND of ORs, each OR has 3 literals), is it satisfiable? Reduction from SAT to 3-SAT: Each clause is converted to CNF with ≤3 literals per clause using auxiliary variables.

3.3 Clique

Problem: Does a graph contain a complete subgraph of size k? Reduction from 3-SAT: Create a graph where each clause has a triangle of its literals; connect literals that are not contradictory. An independent set of size m (clauses) gives a satisfying assignment.

3.4 Vertex Cover

Problem: Is there a set of k vertices that touches every edge? Relation to Independent Set: A set C is a vertex cover iff V\C is an independent set. Reduction from Independent Set:

(G, k) \to (G, n-k)

3.5 Subset Sum

Problem: Given numbers a₁, ..., aₙ and target T, is there a subset summing to T? Reduction from Vertex Cover: Create numbers encoding which vertices cover which edges.

4. NP-Completeness Proof Template


text
To prove problem X is NP-complete:
1. Show X ∈ NP:
   - Give a polynomial-time verifier for solutions
2. Show X is NP-hard:
   - Choose a known NP-complete problem Y
   - Construct reduction f: Y → X
   - Prove: x ∈ Y ⇔ f(x) ∈ X
   - Show f runs in polynomial time

4.1 Worked Proof: Vertex Cover is NP-complete

Step 1: VC ∈ NP Given a graph G=(V,E), integer k, and a candidate set C:

Check |C| = k: O(n)
Verify every edge has at least one endpoint in C: O(m)
Total: O(n + m) — polynomial ✓ Step 2: VC is NP-hard (reduce from Independent Set)
Given instance of IS: (G, k), ask does G have independent set ≥ k?
Let n = |V|. Create instance of VC: (G, n - k)
Claim: G has IS of size k ⇔ G has VC of size n-k
Proof: If I is an IS of size k, then V\I is a VC (every edge has at most one endpoint in I, so at least one in V\I). Conversely, if C is a VC of size n-k, then V\C is an IS of size k.

5. 📝 Practice Questions

Q1: What is the difference between NP-hard and NP-complete?

Answer: NP-complete problems are in NP AND NP-hard. NP-hard problems are at least as hard as any NP problem but may not be in NP themselves. For example, the optimization version "find the minimum vertex cover" is NP-hard but not NP-complete (it's not a decision problem, so not in NP). Q2: Show that if P = NP, then every NP-complete problem can be solved in polynomial time.

Answer: If P = NP, then every problem in NP is in P. Since NP-complete problems are in NP, they are also in P. Thus there exists a polynomial-time algorithm for SAT, 3-SAT, Clique, etc. Q3: Reduce 3-SAT to Clique. Given formula (x₁∨x₂∨¬x₃)∧(¬x₁∨x₃∨x₄)∧(x₂∨¬x₃∨¬x₄).

Answer: Create graph with 9 vertices (3 per clause). Connect vertices if they're in different clauses and not contradictory. The formula is satisfiable iff there's a 3-clique.

Clause 1: v₁₁(x₁), v₁₂(x₂), v₁₃(¬x₃)

Clause 2: v₂₁(¬x₁), v₂₂(x₃), v₂₃(x₄)

Clause 3: v₃₁(x₂), v₃₂(¬x₃), v₃₃(¬x₄)

Edges connect compatible literals across clauses. A 3-clique picks one literal per clause that can all be true simultaneously. Q4: Why is the Cook-Levin theorem important?

Answer: Cook-Levin was the first proof that SAT is NP-complete. It established the technique of reduction for proving NP-hardness and showed that the question "does SAT have a polynomial-time algorithm?" is equivalent to P vs NP. Before Cook-Levin, the concept of NP-completeness didn't exist. Q5: Prove that Dominating Set is NP-complete (hint: reduce from Vertex Cover).

Answer: Given graph G=(V,E) and integer k for Vertex Cover, construct G' = (V∪E, E') where each edge e={u,v} in E becomes a vertex in G', and E' connects edge vertices to their endpoint vertices. A vertex cover of size k in G corresponds to a dominating set of size k in G'. The proof follows from the observation that to dominate edge-vertices, at least one endpoint of each edge must be selected.

6. 🔗 Cross-References

Week 7 - Approximation Algorithms: Coping with NP-hardness
Week 10 - Parameterized Algorithms: Fixed-parameter tractability
BSCS3021 (ToC): Undecidability, Turing machines, time complexity Join Discord PreviousString AlgorithmsNextApproximation Algorithms