Chapter 6 · Watch, then practise
Computational Complexity
Measure resource growth and separate verification from finding a solution.
3 questions · 3 with related videos. Matches are based on playlist titles; broader background matches are labeled.
What to study
- Asymptotic bounds
- Time and space
- P and NP
- Polynomial reductions
- NP-completeness
Chapter playlists
Choose a playlist
Notes
12. Time Complexity
MIT OpenCourseWare · 1:25:37 · Background lecture
Supplementary time-complexity lecture; the tight bound for this particular polynomial is derived below.
1. Growth with input size
An algorithm makes 3n² + 5n + 8 steps. Give a tight asymptotic bound.
The bound is Θ(n²): for sufficiently large n, constant multiples of n² bound the expression above and below. Doubling n makes the dominant term four times larger. Big-O is an upper bound; a tight Θ bound also supplies a matching lower bound for this step-count function.
P vs. NP and the Computational Complexity Zoo
hackerdashery · 10:44
Choose a video · 2 lectures
Pairs the chapter’s P-versus-NP overview with a lecture on P, NP and polynomial-time reducibility.
2. Solving and checking
Why does a polynomial-time verifier not immediately give a polynomial-time solver?
A verifier checks a proposed certificate; finding one may require considering many candidates. P contains decision problems solvable deterministically in polynomial time. NP permits polynomial-length certificates checked in polynomial time. Every P problem is in NP, but this inclusion alone does not show equality.
15. NP-Completeness
MIT OpenCourseWare · 1:25:53
Supplementary NP-completeness lecture for membership and hardness proof obligations.
3. Proving NP-completeness
What two obligations establish that a decision problem B is NP-complete?
Show B belongs to NP, then reduce a known NP-hard problem A to B in polynomial time. Prove that the transformation preserves both yes and no instances. A reduction B → A only shows that A can solve B; it does not establish B’s hardness.