第8章 NP完全性理论

NP问题的字面解释非确定型多项式完全问题

一、背景介绍

1. NP问题的概念

NP问题是计算机科学和数学领域中一个重要的概念，即“非确定性多项式时间”（Non-deterministic Polynomial time），它代表了一类能在多项式时间内被验证的问题。这类问题的解决方案虽然不能在多项式时间内被找到，但一旦有了一个解，却能够在多项式时间内被验证。简而言之，如果一个问题可以在多项式时间内被验证，则它是一个NP问题。

2. 多项式完全问题的概念

多项式完全问题是一类特殊的NP问题，它具有以下两个性质：它是一个NP问题；任何一个NP问题都可以在多项式时间内规约到它。也就是说，如果有一个多项式时间算法能够解决任何一个多项式完全问题，那么就能够解决所有的NP问题。

3. 非确定型多项式完全问题

非确定型多项式完全问题是NP问题中最困难的一类问题，它要求在多项式时间内验证一个解的存在，并且这个验证需要非确定性算法。换言之，虽然这类问题的解可以在多项式时间内被验证，但却无法在多项式时间内被求解。非确定型多项式完全问题是计算理论中一个极具挑战性的问题。

二、定义和性质

1. 非确定型多项式完全问题的定义

非确定型多项式完全问题是指一个问题，如果它是一个NP问题，并且任何一个NP问题都可以在多项式时间内归约到它，那么它就是一个非确定型多项式完全问题。每一个非确定型多项式完全问题都是NP问题，但不是所有的NP问题都是非确定型多项式完全问题。

2. 非确定型多项式完全问题的性质

非确定型多项式完全问题具有以下一些重要性质：

（1）困难性：非确定型多项式完全问题是计算上的一类最困难问题，它们无法在多项式时间内被求解。

（2）通用性：任何一个NP问题都可以在多项式时间内归约到非确定型多项式完全问题，因此解决了一个非确定型多项式完全问题就意味着可以解决所有的NP问题。

（3）实际意义：非确定型多项式完全问题在实际生活中具有广泛的应用，例如在计划问题、调度问题、网络设计等方面都有重要的地位。

第五章 可归约性

定理5.1：HALTTM是不可判定的。

证明：为得到矛盾，假设TM R判定HALTTM，由之可以构造TM S来判定

ATM, 其构造如下：

S=“在输入上，此处是TM M和串w 的编码：

1) 在输入上运行TM R。

2)如果R拒绝，则拒绝。

3)如果R接受，则在w 上模拟M，直到它停机。

4)如果M已经接受，则接受；如果M已经拒绝，则拒绝。

显然，如果R判定HALTTM，则S判定ATM。因为ATM是不可判定的，

故HALTTM也必定是不可判定的。

定理5.2：ETM 是不可判定的。

构造TM M1：M1=“在输入x上：

1)如果x≠w，则拒绝。

2)如果x=w，则在x上运行M，当M接受时，就接受。”

假设TM R判定ETM。如下构造判定ATM的TM S:

S=“在输入上，此处是TM M和串w的编码：

1) 用M和w的描述来构造上述TM M1。

2)在输入< M1 >上运行R。

3)如果R接受，则拒绝；如果R拒绝，则接受。”

定理5.3：REGULARTM是不可判定的。

设R是判定REGULARTM 的一个TM，下面构造判定ATM的TM S。

S的运行方式如下：

S=“对于输入，其中M是TM，w是串：

1)构造下述TM M2：

M2=“在输入x上：

a) 如果x具有形式0n1n，则接受。

b)如果x不具有此形式，则在输入w上运行M。如果M接受w，则接受。”

2)在输入上运行R。

3) 如果R接受，则接受；如果R拒绝，则拒绝。”

定理5.4：EQTM是不可判定的。

设TM R判定EQTM。如下构造判定ETM 的TM S：

S=“对于输入，其中M是TM：

1)在输入上运行R，其中M1是拒绝所有输入的图

灵机。

2)如果R接受，则接受；如果R拒绝，则拒绝。

如果R判定EQTM，则S判定ETM。但由定理5.2，ETM是不可判定的，故EQTM也是不可判定的。

定义概念题目：

第三章：

1. 图灵机：是一种精确的通用计算机模型，能模拟实际计算机的所有

计算行为，它的核心是转移函数δ，它说明了机器如何从一个格局走到

下一个格局。对于图灵机，δ的形式如下：Q×Γ→Q×Γ{L,R},图灵机

是一个7元组（Q，∑，Γ，δ，q 0,qaccept,qreject）.其中Q，∑，Γ都

是有穷集合，并且1）Q是状态集；2）∑是输入字母表，不包括特殊空

白符号凵，3）Γ是带字母表，其中凵∈Г，∑∈Г4）δ

2. 格局：图灵机的计算过程中，当前状态，当前内容和读写头当前位

置组合在一起。例如：1011q701111：当前状态q7，当前读写头位置在

第二个0上。

定义3.2 如果一个语言能被某一个图灵机识别，则称该语言是图灵可识

别的（递归可枚举语言）

定义3.2 如果一个语言能被某一个图灵机判定，则称该语言是图灵可判

定的简称可判定的（递归语言）

3.图灵机的变形：多带图灵机、非确定型图灵机、枚举器。

每个

4.枚举器：他是图灵机的一种变形，是带有打印机的图灵机，图灵机把

打印机当作输出设备，从而可以打印串，每当图灵机想在打印序列中增

加一个串时，就把此串送到打印机。一个语言是图灵可识别的，当且仅

当有枚举器枚举它。

5.图灵机的术语：形式化描述，实现描述，高水平描述。

第四章：

1.可判定的语言有：（ADFA、ANFA、AREX、EDFA、EQDFA 是正则语言）、

（ACFG、ECFG 是上下无关语言）❶每个上下文无关语言都是可判定的。

2.不可判定的语言有:：EQCFG、ATM 、停机问题、HALTTM 、ETM 、

REGULARTM 、EQTM 、 ELBA 、ALLCFG 、PCP

ATM =｛｜M是TM，ω是串，M接受ω｝是不可判定的。

证明：假设证ATM 是可判定的，下面将由之导出矛盾。设H是ATM 的判定

器。令M是一个TM，ω是一个串。在输入上，如果M接受ω，则H

就是停机且接受ω；如果M不接受ω，则H也会停机，但拒绝ω。换句话

1

可满足性问题与消解法

1. 可满足性问题

回顾：若一个命题公式不是永假式，则称为可满足的。

可满足性问题：判断一个命题公式是不是可满足的。在计算机科学和算法理论中专门指合取范式的可满足性问题，记为SAT。是理论计算机科学中的一个核心问题。属于NP完全问题。

算法的时间复杂度：

多项式时间算法与指数时间算法比较：

220=1百多万

230=10多亿

250=1千多亿亿

2100=1万多亿亿亿

P类问题：多项式时间可解的问题。目前许多实际问题的算法的时间复杂度是O(n3)

NP类问题：多项式时间可验证的问题。素数分解问题。大量的实际问题都属于NP类问题。

P与NP问题：P=NP？

NP完全性：许多看似简单的问题事实上都是NP完全的。

Cook定理：SAT是NP完全的。

其它NP完全问题：旅行商问题、中国邮递员问题、子集和问题。

2

2. 消解法

设C1，C2是两个简单析取式，其中C1含有某文字l，C2含l的补。删除C1中的文字l和C2中的文字l的补，并将二者剩下的文字合并为一个简单析取式，称为C1与C2的消解式或者消解结果（resolvant），记为Res(C1, C2)。特别地，若1Cl1=l，2cCl，则

12, 0ResCC

定理 1212, CCResCC

3. 否证

定义 设S是一个合取范式，12,,,nCCC是一个简单析取式序列。若 ，则称该序列为由S 导出Cn的消解序列。若Cn=0，则称该消解序列为S的否证（refutation）。

注意，若由S通过消解可以 导出Cn，则nSC。因此，

定理（消解的正确性）若存在S的否证，则S是不可满足的，即永假式。

因此，用消解法可以解决可满足性问题。

定理（消解的完备性）若合取范式S是永假式，则存在S的否证。

注：消解是一种重要的比较有效的证明方法。