Opening Computational Complexity
Computational Complexity
- Length
- 51 min
- Level
- Undergraduate
- Recorded
- MIT2013
Chapter 1 of 7: Before the lecture
Proves most decision problems uncomputable by a counting argument, then reduces 3-Partition to Tetris to show hardness.
Computational complexity sorts problems by how much time they need, separating those with polynomial-time algorithms from intractable ones. Demaine starts with the classes P, EXP and R, then shows that almost every decision problem is uncomputable. Programs are countable while decision problems correspond to real numbers, which are not. He defines NP twice: through a lucky nondeterministic algorithm, and as problems whose solutions can be checked in polynomial time, with Tetris as the running example. After stating the P versus NP question, he presents NP-completeness and reductions, using them both to design algorithms and to prove hardness from 3-Partition. The session assumes asymptotic notation, graph algorithms such as Bellman-Ford and Dijkstra, and basic cardinality.
Computational complexity sorts problems by how much time they need, separating those with polynomial-time algorithms from intractable ones. Demaine starts with the classes P, EXP and R, then shows that almost every decision problem is uncomputable. Programs are countable while decision problems correspond to real numbers, which are not. He defines NP twice: through a lucky nondeterministic algorithm, and as problems whose solutions can be checked in polynomial time, with Tetris as the running example. After stating the P versus NP question, he presents NP-completeness and reductions, using them both to design algorithms and to prove hardness from 3-Partition. The session assumes asymptotic notation, graph algorithms such as Bellman-Ford and Dijkstra, and basic cardinality.

This lecture
Lecture 23 of 31 of Introduction to Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in