定义：如果存在函数<<latex($$f:\Sigma^*\mapsto\Sigma^*$$)>>的多项式界限的Turing机M，则f称为'''多项式时间可计算的'''。设<<latex($$L_1,L_2\subseteq\Sigma^*$$)>>是语言，设<<latex($$\tau:\Sigma^*\mapsto\Sigma^*$$)>>是多项式时间可计算得函数。如果对每个<<latex($$x\in\Sigma^*$$)>>下列关系成立：<<latex($$x\in L_1$$)>>当且仅当<<latex($$\tau(x)\in L_2$$)>>，那么<<latex($$\tau$$)>>称为从L1到L2的多项式归约。

双机调度

背包问题

引理：多项式归约传递性

定义：设<<latex($$L\subseteq\Sigma^*$$)>>是语言，如果<<latex($$L\in P$$)>>并且对每一个语言<<latex($$L'\in NP$$)>>存在从L'到L的多项式归约，那么L称为是NP完全的。

定理：设L是NP完全语言。那么P=NP当且仅当<<latex($$L \in P$$)>>

有界铺砖

定理：有界铺砖是NP完全的。

Cook定理：可满足性是NP完全的。

定理：三元可满足性是NP完全的。

定理：最大可满足性是NP完全的。

定理：恰当覆盖是NP完全的。

定理：Hamilton圈是NP完全的。

定理：无向Hamilton圈是NP完全的。

定理：旅行商问题是NP完全的。

定理：背包问题是NP完全的。

推论：划分和双机调度都是NP完全的。

定理：独立集是NP完全的。

定理：团和顶点覆盖是NP完全的。

定理：无星号正则表达式的不等价性是NP完全的。