For the time-bounded classes, we show a weaker result.

#### Theorem 1.23

*Proof*

A nondecreasing function *f*(*n*) is called *superpolynomial* if

for all *i* ≥ 1. For instance, the exponential function 2^{n} is superpolynomial, ...

Get *Theory of Computational Complexity, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.