定义：如果存在函数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的多项式归约。
定义：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完全的。