计算复杂性

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

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

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

定义：NP

计算复杂性 (2008-02-23 15:34:18由localhost编辑)