定义:多项式时间可计算。多项式归约。
定义: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完全的。