第4讲第P类NP类NPC类2doc.docx
《第4讲第P类NP类NPC类2doc.docx》由会员分享，可在线阅读，更多相关《第4讲第P类NP类NPC类2doc.docx（10页珍藏版）》请在冰点文库上搜索。
第4讲第P类NP类NPC类2doc
上次内容：
（1）确定图灵机与P类，DTM多项式时间可解的-----P类
（2）非确定图灵机NP类，NTM多项式时间可解的----NP类----多项式时间可验证的（没法严格表达，所以用非确定图灵机来表达）。
（3）多项式变换与NP，上次讲到什么是多项式变换。
多项式变换的含义：
●1=<1,L1,1>；2=<2,L2,2>
●变换f：
1*2*，IL1，f（I）L2，1（I）=2（f（I））
●f变换可以在p（|I|=n）时间内计算完成。
则f称为由1到2的多项式规约。
NP问题的定义，一个问题是多项式时间可验证的含义，一个实例若回答是，当然能猜出来，所以能正确回答yes。
若一个实例回答否，两种情况，回答NO，或不停机。
NP问题可以认为是若实例回答是，则存在不确定多项式时间算法正确回答的问题类。
猜测部件定义回答NO的实例不好定义。
希望说明如下道理：
若1可以多项式归约到2，则若2存在多项式算法，则1也有多项式算法。
前面的多项式规约进一步修改如下：
认为与前面的定义等价。
●1=<1,L1,1>；2=<2,L2,2>
●变换f：
，IL1，f（I）L2，
1（I）=1（yes）2（f（I））=1（yes），充分必要的。
IY1f（I）Y2。
不关心回答no的实例。
实际前面NTM定义中就只关心回答yes的实例。
与猜测能力有关。
如果定义猜测能力过于复杂，神的能力就太大了。
P问题可以在多项式时间回答是或否。
●f变换可以在p（|I|=n）时间内计算完成。
*不关心回答no的实例。
以后证明都用此定义。
再解释不确定Turing机：
（1）猜测部件把解写在从-1开始向左的存储带上。
最多写输入长度的多项式个方格。
（2）我们自己编写的严正程序直接使用猜测解带方格中的内容，没写直接用。
若有一个特殊问题，任意一个NP问题均可多项式规约到该问题，则该问题非常特殊。
严格定义时，要求是NP类问题。
这样的问题成为NP-Complete，若NP-Complete问题可以多项式时间解决，则其他所有NP问题都可以在多项式时间解决。
●首先要搞清楚，现在我们研究的问题是多项式时间可验证的问题类，最后只需要回答是和否即可以。
●有很多问题不是多项式时间可验证的，那个留到以后再说。
因此也不是NPC的。
多项式变换的符号：
引理3.1：
若12，2P，则1P。
//1，2NP
是为什么？
注意一点，当多项式可解时，否的实例也能在多项式时间回答。
引理3.2：
12，23，则13
定义3.10：
12，21，则称1和2等价多项式等价。
定义3.11：
NP，1NP，1，则称是NP-Complete的。
NP-完全的。
其他人有很多叫法。
简称NPC问题。
若是NPC问题，有多项式时间算法，则任意NP问题都有多项式时间求解算法。
定理3.12：
若有，NPC，则下述
（1）
（2）等价。
（1）PNP；
（2）P
若1NPC，2NP，12，则2NPC
这是最重要的一个定理。
只要有了一个NPC，其他问题也可以证明NPC了。
下面的问题是寻找第一个NPC问题。
§3.5Cook定理
任意一个NP问题都有一个多项式时间验证程序唯一代表改问题。
验证结果回答yes或no。
SAT的例子：
Y=（u1
u5）（u2u3
）（
u4u5）（u1
）是否存在真值指派使Y=1。
Instance:
U={u1,u2,u3,u4,u5},C={C1,C2,C3,C4}
Query:
IfthereisassignationofUsuchthateveryclauseofCissatisefied.
定理3.4：
SATNPC。
证明：
（1）SATNP，首先要验证这个。
不验证不能说明是NPC。
*不属于NP是否属于NPC?
，不属于。
（2）将任意一个NP问题多项式规约到sat。
每个NP问题有一个对应一个NTM的多项式时间验证程序。
该验证程序最后回答yes。
任意一个NP问题的实例放在NTM存储带上，若回答yes，NTM程序多项式时间步验证给出正确回答。
把求解任意一个NP问题的NTM规约到sat。
设NTM描述为：
描述问题需要符号集
●={s0,s1,s2,…,sm}
●Q={q0,q1=qy,q2=qn,q3,…,qr}
●（qi,si）=（qi’,si’,i），变化规则早已确定了，就是程序。
●P（n）：
M接受输入I，|I|=n，按照计算，对于猜测的解，经过不超过P（n）步计算，到达停机态，P（n）是n的多项式函数。
任意问题的描述：
实例：
询问：
是否存在一个解x1,…,xi，满足条件，y1,y2,…,yj。
每个实例都存放在读写带上了，要把这个实例变成SAT的实例。
要借助别的东西，借助求解验证程序。
开始规约：
变量描述求解过程，项约束求解中程序遵循的规则。
1．定义三种变量描述NTM的求解状态，
（1）Q[i,k]:
描述状态，0iP（n），0kr，在时刻i，M处于状态qk，（r+1）（P（n）+1）个这样的变量。
（2）H[i,j]：
描述读写头位置，0iP（n），-P（n）jP（n），在时刻i，M读写头正扫描带方格j。
（2P（n）+1）（P（n）+1）个变量。
（3）S[i,j,L]：
描述带方格内容，0iP（n），-P（n）jP（n），0Lm，在i时刻带方格j中的内容为符号sL，（m+1）（2P（n）+1）（P（n）+1）。
解释：
从0到p（n）每一个时刻的Turing机状态，读写头位置，读写带上的符号。
2．NTM程序接受判定问题的实例I，M运行中应遵循下述规则。
G1
在时刻i，M确切处在一个状态，q0,…,qr
G2
在时刻i,读写头确切地扫描一个带方格。
G3
在时刻i,每个带方格确切地含有一个符号，中的。
G4
在时刻0，对于输入I，计算处于验证阶段的起始状态。
G5
在时刻P（n），M处于qy状态，接受I。
G6
转换函数决定i时刻到i+1时刻的状态变化。
G1中的项如下构成：
在时刻i，M确切处在一个状态，q0,…,qr
（1）{Q[i,0],Q[i,1],…,Q[i,r]}，0iP（n）
（2）{
，
}，0iP（n），0j,j’r
（1）的个数：
P（n）+1
（2）的个数：
（P（n）+1）
G2的构成如下：
在时刻i,读写头确切地扫描一个带方格。
（1）{H[i,-P（n）]，H[i,-P（n）+1]，…，H[i,0]，…，H[i,P（n）]}
0iP（n）读写头位于上述位置。
至少一个为真的。
但不能量个同时为真。
（2）{
，
}，0iP（n），-P（n）jj’P（n）
读写头不能同时指向两个带方格，所以综合
（1）
（2），每个时刻，读写头总指向固定一个带方格。
（1）的个数：
P（n）+1
（2）的个数：
（P（n）+1）
G3的构成：
在时刻i,每个带方格确切地含有一个符号，中的。
（1）{S[i,j,0],S[i,j,1],…,S[i,j,m]}，0iP（n），-P（n）jP（n）
i时刻，j号带方格中的内容可能是s1,…,sm
（2）{
，
}，0iP（n），-P（n）jP（n），0k,k’m
一个时刻一个方格中不可能含有两个符号。
（1）的个数：
（P（n）+1）（2P（n）+1）。
（2）的个数：
（P（n）+1）（2P（n）+1）
G4的构成：
在时刻0，对于输入I，计算处于验证阶段的起始状态。
{Q[0,0]}：
0时刻状态为q0
{H[0,0]}：
0时刻读写头位于0号带方格
{S[0,0,k0]}，{S[0,1,k1]}，…，{S[0,n,kn]}
{S[0,n+1,0]}，{S[0,n+2,0]}，{S[0,P（n）,0]}
0时刻带方格中的内容分别为：
。
其他带方格中是什么内容？
G5：
在时刻P（n），M处于qy状态，接受I。
{Q[P（n）,1]}，时刻P（n）的NTM状态为qy=q1。
接受状态。
G6=G61G62，两个子项，转换函数决定i时刻到i+1时刻的状态变化。
G61：
保证在时刻i，若读写头不扫描带方格j，则在时刻i+1，j带方格的内容与i时刻j带方格的内容相同。
{
H[i,j],S[i+1,j,L]}，0iP（n），-P（n）jP（n），0Lm
G61的个数：
（P（n）+1）（2P（n）+1）（m+1）
G62：
当NTM程序从一个状态转到另一个状态时，状态变化，读写头移动，符号改变遵从函数。
（qk,sL）=（
）
（1）{
H[i+1,j+]}
i时刻的状态为qk，读写头位置为j，j方格中的符号为sL
则读写头移动为。
●0iP（n），-P（n）jP（n），0kr，0Lm
所以
（1）的子句个数是：
（P（n）+1）（2P（n）+1）（r+1）（m+1）
（2）{
，Q[i+1,k’]}
0iP（n），-P（n）jP（n），0kr，0Lm。
所以
（2）的子句个数是：
（P（n）+1）（2P（n）+1）（r+1）（m+1）
（3）{
，S[i+1,j,L’]}
0iP（n），-P（n）jP（n），0kr，0Lm
（3）的个数也不超过：
（P（n）+1）（2P（n）+1）（r+1）（m+1）
●上面是规约，首先说明这个规约是多项式规约，G1,G2,G3,G4,G5,G6都是多项式个clause，因此是多项式规约。
●下面说明规约后的计算情况：
若任意问题的实例I回答yes，则NTM程序最后停机在qy，此时必存在一个sat变量的真值指派使每个项均满足。
01n-1P（n）
若sat实例存在真值指派使每个项均满足，则最后NTM会停机在yes态，相应问题的实例回答yes。
这就证明了第一个NP-complete问题。
再说明：
*为什么SAT能多项式时间可解，则NTM就不用猜测解了。
*s[0,-1,s1]，s[0,-1,s2]，…，s[0,-1,sm]，
*s[0,-2,s1]，s[0,-2,s2]，…，s[0,-2,sm]
*…………
*s[0,-P（n）,s1]，s[0,-P（n）,s2]，…，s[0,-P（n）,sm]
*0时刻的内容，由SAT实例计算出来。
Cook想了一个办法说明问题难度，任意一个NP问题都可以多项时间规约到SAT问题，即若SAT问题能够多项式时间解决，则其他所有NP问题都能多项时间解决。
正确回答是和否。
若1NPC，2NP，12，则2NPC。
已知satNPC，从SAT开始证明其他NPC，万事开头难。
已经证明了SAT是NPC了，其他问题是NPC的证明肯定与SAT不同了，
定理4.1：
3satNPC
证明在后面，先多讲几个问题
实例：
布尔变量集合：
U={u1,…,un}，
项集合：
C={C1,C2,…,Cm}，|Ci|=3
询问：
是否存在U的真值指派使C中所有项均满足？
●3对集问题
实际含义：
100个编程人，100个数学推导，100个写文章的，组成100个数学建模队，但并不是任意两人都可以分到同一队，所以每个人可以与他人共事的选择并不是任意的。
能组成吗？
拉登组成恐怖小组。
问题描述：
实例：
集合：
W,X,Y，MW*X*Y。
|W|=|X|=|Y|=q。
询问：
是否存在M的子集M’M，使|M’|=q，M’中没有任意两个3元组有相同的分量。
组队问题。
升级会员 