Degrees of Hardness

Like stones, we can categorize problems by how hard they are:

• not computable: halting problem.
• computable, but not in less than exponential time: succinct circuit value, generalized checkers.
• computable in polynomial time, but not in linear time: sorting using only comparisons (Section 9.1).
• computable in linear time: topological sort.

All of these are tight: can't do any better. The NP-complete problems are frustrating because we know how to solve them in exponential time, but we don't know we can't solve them in polynomial time. Big gap!