1209
备注:
|
← 于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的多项式归约。 |
行号 3: | 行号 3: |
定义:NP完全 | 双机调度 |
行号 5: | 行号 5: |
定理:设L是NP完全语言。那么P=NP当且仅当[[latex($$L \in P$$)]] | 背包问题 引理:多项式归约传递性 定义:设<<latex($$L\subseteq\Sigma^*$$)>>是语言,如果<<latex($$L\in P$$)>>并且对每一个语言<<latex($$L'\in NP$$)>>存在从L'到L的多项式归约,那么L称为是NP完全的。 定理:设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完全的。