Computational Complexity Foundations
Why Complexity Theory Matters
Core Idea
Computational complexity studies the resources required to solve problems, typically time and space. It gives a principled way to compare algorithms, prove lower bounds, and understand which problems are feasible at scale.
Essential Complexity Classes
Central Question
The famous vs. question asks whether every efficiently verifiable problem is also efficiently solvable.
Which class contains problems solvable in polynomial time on a deterministic machine?
By definition, is the class of decision problems solvable in polynomial time by a deterministic Turing machine.
Correct answer:
State the difference between and in one sentence.
The key distinction is solution finding versus solution checking.
Correct answer: P problems can be solved in polynomial time; NP problems can be verified in polynomial time.
Deterministic vs. Nondeterministic Perspectives
Deterministic computation
- A single computation path
- Direct algorithmic execution
- Models
Nondeterministic computation
- Multiple hypothetical branches
- Verification-oriented view
- Models
Typical Complexity-Theoretic Proof Strategy
-
1
Show membership in a class such as or .
-
2
Reduce from a known hard problem using a polynomial-time many-one reduction.
-
3
Use closure properties or diagonalization where appropriate.
-
4
Interpret the result as evidence of intrinsic intractability.
A polynomial-time many-one reduction from problem to problem implies what?
If and has a polynomial-time algorithm, then does too.
Correct answer: If is easy, then is easy
From Decision to Optimization
Many practical problems are optimization problems rather than decision problems. Complexity theory often studies a decision version first, because it fits cleanly into classes like -complete, and then transfers hardness to optimization through approximation-preserving arguments.