We've seen that if we want to make progress in complexity, then we need to talk about asymptotics: not which problems can be solved in 10000 steps, but for which problems can instances of size n be solved in cn^{2} steps as n goes to infinity? We met TIME(f(n)), the class of all problems solvable in O(f(n)) steps, and SPACE(f(n)), the class of all problems solvable using O(f(n)) bits of memory.

But if we really want to make progress, then it's useful to take an even coarser-grained view: one where we distinguish between polynomial and exponential time, but not between O(n^{2}) and O(n^{3}) time. From this remove, we think of any polynomial bound as “fast,” and any exponential bound as “slow.”

Now, I realize people will immediately object: ...

Start Free Trial

No credit card required