|
大小: 1458
备注:
|
← 于2008-02-23 15:34:19修订的的版本4 ⇥
大小: 1458
备注: converted to 1.6 markup
|
| 删除的内容标记成这样。 | 加入的内容标记成这样。 |
| 行号 1: | 行号 1: |
| 定义：如果存在函数[[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($$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的多项式归约。 |
| 行号 9: | 行号 9: |
| 定义：设[[latex($$L\subseteq\Sigma^*$$)]]是语言，如果[[latex($$L\in P$$)]]并且对每一个语言[[latex($$L'\in NP$$)]]存在从L'到L的多项式归约，那么L称为是NP完全的。 | 定义：设<<latex($$L\subseteq\Sigma^*$$)>>是语言，如果<<latex($$L\in P$$)>>并且对每一个语言<<latex($$L'\in NP$$)>>存在从L'到L的多项式归约，那么L称为是NP完全的。 |
| 行号 11: | 行号 11: |
| 定理：设L是NP完全语言。那么P=NP当且仅当[[latex($$L \in P$$)]] | 定理：设L是NP完全语言。那么P=NP当且仅当<<latex($$L \in P$$)>> |
定义：如果存在函数<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>的多项式界限的Turing机M，则f称为多项式时间可计算的。设<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>是语言，设<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>是多项式时间可计算得函数。如果对每个<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>下列关系成立：<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>当且仅当<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>，那么<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>称为从L1到L2的多项式归约。
双机调度
背包问题
引理：多项式归约传递性
定义：设<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>是语言，如果<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>并且对每一个语言<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>存在从L'到L的多项式归约，那么L称为是NP完全的。
定理：设L是NP完全语言。那么P=NP当且仅当<<latex: 执行失败 [Missing parentheses in call to 'print'. Did you mean print(...)?] (see also the log)>>
有界铺砖
定理：有界铺砖是NP完全的。
Cook定理：可满足性是NP完全的。
定理：三元可满足性是NP完全的。
定理：最大可满足性是NP完全的。
定理：恰当覆盖是NP完全的。
定理：Hamilton圈是NP完全的。
定理：无向Hamilton圈是NP完全的。
定理：旅行商问题是NP完全的。
定理：背包问题是NP完全的。
推论：划分和双机调度都是NP完全的。
定理：独立集是NP完全的。
定理：团和顶点覆盖是NP完全的。
定理：无星号正则表达式的不等价性是NP完全的。