Reductions, NP-Completeness, and Problem Hardness
Reductions as a Universal Language
Reduction Concept
A reduction transforms instances of one problem into instances of another while preserving answers. If problem reduces to problem , then a solver for yields a solver for .
Hardness Vocabulary
A problem is NP-complete if it is...
NP-complete problems are exactly the problems that lie in and are -hard.
Correct answer: in and -hard
Why is SAT historically important in complexity theory?
The Cook-Levin theorem anchored the entire theory of NP-completeness.
Correct answer: It was the first problem proven NP-complete, establishing the NP-completeness framework.
Proving NP-Completeness
-
1
Show the target problem is in .
-
2
Choose a known NP-complete source problem, such as -SAT or CLIQUE.
-
3
Construct a polynomial-time reduction from the source to the target.
-
4
Prove correctness in both directions.
-
5
Conclude NP-completeness.
Common Pitfall
To prove a problem is NP-hard, you reduce a known hard problem to it — not the other way around.
Reduction Directions
Source to target
- Used to prove target hardness
- The standard NP-hardness direction
- Shows the target is at least as hard as the source
Target to source
- Usually proves little about hardness
- Often the wrong direction for reductions
- Can imply the source is no harder than the target
Which direction is standard for proving a new problem is NP-hard?
To show is hard, transform a known hard problem into .
Correct answer: Reduce a known NP-complete problem to
Why Hardness Results Matter in Practice
Hardness results do not say a problem cannot be solved; they say that a general polynomial-time algorithm is unlikely unless foundational complexity assumptions fail. This guides practitioners toward heuristics, approximation, parameterization, or special-case structure.