定义：多项式界限。多项式可判定

定理：P在补运算下封闭。

定理：<<latex($$E=\lbrace"M""\omega":M\ accepts\ input\ \omega\ after\ at\ most\ 2^{|\omega|}\ steps \rbrace. E \notin P$$)>>

定义：NP