Applying NP-Completeness
December 1, 2025
Recall definitions of P, NP, and Expo
- P: Decision problems solvable in polynomial time
- NP: Decision problems with polytime verification (= NPoly)
- Expo: Decision problems solvable in exponential time
- Remember: We restrict to decision problems in this chapter
Key relationships: We know P \(\subseteq\) NP \(\subseteq\) Expo, but are these proper subsets? This is perhaps the most famous open question in computer science!
Is there anything in NP but not in P?
- “Middle region”: This is where NP-complete problems live, if P \(\neq\) NP
- Question: Are there any computational problems in this region?
- Belief: Yes, thousands of problems are in NP but not in P
Try to grasp “P versus NP” debate
- One understanding: If P = NP, the classes are identical
- Alternative view: If P \(\neq\) NP, there’s a “gap” between them
- Key insight: We don’t know which view is correct!
- Reminders about this definition:
- Focus is on complexity class of decision problems
- P: problems solvable in polynomial time
- NP: problems verifiable in polynomial time
Alternative view of P versus NP
- Scenario 1: P = NP is unlikely but possible
- Scenario 2: P \(\neq\) NP is widely believed
- Importance: This affects cryptography, optimization, and much more
- Deep insight: Verification might be fundamentally easier than solving
- Don’t forget the “middle group” from the prior diagram!
Tree-based interpretation
- Deterministic: Must search tree sequentially
- Nondeterministic: Can explore all branches simultaneously
- P = NP would mean: Sequential search is as good as parallel search
- P \(\neq\) NP would mean: Parallel search provides exponential speedup
- Let’s revisit a computational tree to understand this further!
Computation tree visualization
- Tree structure: Each branch represents a possible solution path
- Nondeterministic advantage: Explore all paths at once
- Deterministic limitation: Must try paths one at a time
- Question: Can deterministic programs simulate this efficiently?
Another tree-based view
- If the answer was yes, then P = NP!
- Looking ahead:
- Next, we’ll define NP-completeness
- Show how NP-complete problems are the “hardest” in NP
- Thousands of problems are polyequivalent to:
- CircuitSAT, SAT, or 3-SAT
- UHC or DHC
- We can define a group of problems that are all “equally hard”
Many problems are polyequivalent
- Claim: These problems are all polyequivalent
- Can be proved: But we didn’t prove all reductions
- Equal difficulty: If we ignore polynomial factors
- Thousands known: Many other problems at this level
- Next: Define this class as NP-complete
Classical definition of NP-complete
- Two conditions: Must be in NP and all NP problems reduce to it
- Example: DHC is NP-complete (although we haven’t proved it yet)
- Surprising fact: All NP problems polyreduce to DHC!
- This is strange but true: One problem captures all of NP
- However, let’s start with the Cook-Levin theorem!
Definition using SAT
- Because of Cook-Levin: We can use SAT as a starting point
- Easier definition: Just reduce from SAT instead of all NP problems
- Exercise: Why is this definition equivalent to the “classical one”?
- However, a more general definition is actually possible!
General definition using any NP-complete problem
- Replace SAT: Use any known NP-complete problem \(C\)
- Exercise: Why is this definition equivalent to earlier ones?
- Flexibility: Choose reduction source that’s most convenient
Polyequivalence definition
Definition: NP-complete problem is polyequivalent to any NP-complete problem; note that this moves in both directions! Polyequivalence: Bidirectional reductions between problems Key insight: All NP-complete problems are equally hard Implication: Solving one solves them all Elegant: Captures the essence of NP-completeness
First reformulation of P versus NP
- P = NP: Equivalent to saying every NP-complete problem is in P
- P \(\neq\) NP: Equivalent to saying no NP-complete problem is in P
- Simplified question: Focus on NP-complete problems
Second reformulation of P versus NP
- Alternative phrasing: Uses specific NP-complete problem
- Same question: Different way to express P versus NP
- All equivalent: Various formulations, one open problem
Revisit the diagram
- Visual representation: Shows the question graphically
- Middle region question: Are there any computational problems here?
- Exercise: Why are these definitions equivalent to earlier ones?
Definition of NP-hard
- Key property: All NP problems polyreduce to it
- Not necessarily in NP: Problem could be “outside NP”
- Relationship: For problems in NP, NP-hard = NP-complete
- Examples: Nondecision TSP, nondecision UHC, nondecision SAT
Decision problem summary
- Restriction: This diagram applies to decision problems only
- Relationships: Shows how classes relate to each other
- NP-complete: At the “boundary” between P and NP
- What would happen if we could prove that TSP was in P?
Nondecision problem summary
- Broader view: Includes optimization and search problems
- NP-hard region: Contains problems outside NP
- Complete picture: Shows full complexity landscape
The web of NP-completeness
- Arrows: Represent polyreductions between problems
- Solid black: Reductions we proved in this book
- Dotted: Reductions from other sources
- Grey: Follow from NP-completeness of CircuitSAT