P与NP问题的相对化关系及逻辑推理

1可分性和单向函数约翰·罗杰斯2000年7Abstra t我们解决了下列五个命题之间关系的所有相对化问题P=NPP=UPP=NP\oNP所有不相交的NP集对都是P-可分的.所有不相交的oNP集合对都是P-可分的.我们第一次广泛地使用各种不同的类属词来概括必要的相对世界。1产品介绍为了更好地理解P和NP之间的关系，研究NP内部的语言结构是有益在本文中，我们研究了NP和oNP集的不可分离性，并将其与复杂性理论中的其他重要命题联系起来。考虑以下五个命题：(P1)P = NP（P2）P =UP(P3)P = NP\oNP(P4)所有不相交的NP集合对都是P-可分的。(P5)所有不相交的oNP集合对都是P-可分的。目前，我们不知道这些命题是否正确。事实上，对于每个人来说，存在一个相对于命题为真的命题和另一个相对于命题为假的命题，因此证明或反驳它们中的任何一个都需要非相对化证明技术。然而，我们确实知道它们之间的逻辑关系。 比较容易证明，（P1）蕴涵余项，（P4）和（P5）都蕴涵（P3）。Grollmann和Selman [GS88]表明（P4）也蕴涵（P2）。美国芝加哥大学计算机系，邮编：60637;电子邮件：fortnows. uhi ago.edu。部分由NSF资助CCR 92-53582支持。美国芝加哥德保罗大学CTI学院，邮编60604。电子邮件：rogers s.depaul.edu.工作完成，而在芝大学前，而被部分支持的国家科学基金会资助CCR 92-53582。2我们能证明其他与这些一致的关系吗？我们的主要结果是，已知的含义是唯一的，在每一个相对化的世界。 也就是说，我们证明了一个或者实现其他一致的逻辑关系。我们还研究了一个命题，我们都是命题Q，其中指出，一个很容易找到任何NP机器的一个epting路径，a epts。我们证明了这与（P5）之间的关系1.1Generi ora les当我们有一个无法反驳的命题时，我们可能会试图构造一个相对于它为真的命题。一个经常有效的方法是从定义一组不完备的需求开始，这样，如果满足了一个需求，这个命题就为真。 这之后是分阶段建造的在第0阶段，我们让Orle是空集。在每一个小时苏埃丁在此阶段，我们选择一个需求，并向orle中添加少量的信息，使需求得到满足，同时保证先前满足的需求保持满足。例如，这种结构可以用于构建一个相对于P6 = NP的orle。由于显而易见的原因，这样的构造被称为nite extension构造。定义需求通常很容易，但执行构造和演示它的工作往往是令人不安的。但这暴露了我们正在努力完成的事情。我们更感兴趣的是是否存在一个相对于命题为真的命题，而对命题的特殊形式不感兴趣。这就是generi奥拉莱rst考虑到Mehlhorn [Meh 73]和后来Blum和Impagliazzo [BI 87]提出的复杂性理论是有用的如上所述，我们首先定义一组要求，以便如果满足某个要求，则某些命题将为真。然后我们定义一个一般的条件，它通常是一个关于弦的nite函数。本文的一个重要论点是，遵循Fenner，Fortnow，Kurtz和Li [FFKL 93]的领导，我们经常在条件上强加一种特殊形式，使其更容易满足某些条件。要求类别。当芬纳、福特诺和库尔茨[FFK94]证明了同构猜想成立的一个条件。然后，我们证明，给定任何条件，任何要求，我们一个另一种延伸并满足要求的条件。这表明满足这个要求的条件集是稠密的。然后，我们使用一个简单的参数来表明，有一个ora le，同时，对于每个需求，扩展一些满足该需求的条件，因此ora le满足所有需求。这种方法的优点是它可以证明如何满足个性化的需求而不是关于奥拉的技术细节。它通常也会导致一个更短，更容易理解的证明。1.2相关结果复杂性理论的orle结果的历史始于Baker，Gill和Solovay的论文[BGS 75]。他们构造了A、B、C和D这样的结构，PA = NPAPB 6= NPB = oNPBPC 6= NPC和PC = NPC\ oNPCPD6= NPD\ oNPD且 NPD6= oNPD3注意，相对于A，（P1）成立，所以（P2）到（P5）也成立。Rako[Ra 8 2]是相对化UP的第一个到最好的。他对A和B进行了计算，结果是PA6=oNPA = NPA = UPAPB = NPB\ oNPB = UPB 6= NPBGeske和Grollman [GG8 6]创造了一个这样的词，PC 6= UPC 6= NPCHomer和Selman [HS 92]设计了一个定理A，使得PA6= NPA，但NPA集的所有不相交对都是PA-可分的.我们表明，这是相对于科恩generi ora le。他们还构造了一个方程B，使得PB= UP B6= NP B\oNP B. Grollmann和Selman [GS 88]证明了P=UPi单向函数不存在，NP的所有不相交对是P-可分的i弱单向函数不存在.因此，由于（P3）的否定蕴涵着（P4）的否定，相对于B有弱单向函数，但没有单向函数。这个结果也是我们工作的直接结果。梅尔霍恩是 第一次考虑科恩关于命题的一般性原则，om-当他表明PGNPG[Meh 7 3]是一个复杂的理论时，Blum和Impagliazzo[BI87]，使用Rako[Ra 82]和Hartmanis和Hemahandra[HH 87]的技巧，如果P=PSPACE，则PG = UPG =NPG\oNPG 6= NPG我们将在这里使用他们的一些技术。Impagliazzo和Naor[IN 8 8]以及Cres enzi和Silvestri[CS 9 3]表明，存在一种不确定性，图灵机承认Q命题失败。 也就是说，不存在函数fG2 FP G，如果对每个x2，fG（x）是MG（x）的一条可移动的路。 本文给出了这一结论的一个较简单的证明。当我们考虑相对于一个随机变量R会发生什么时，我们发现下列陈述保持：PR6=NPR[BG 81]，PR6=UP R[KMR 95，IR 89]，存在非P -可分的NP集合的不相交对[GS88，KMR 95，IR 89，Ver 93]，并且存在非P-可分的oNP集合的不相交对[Ver 93]。P R是否=NPR\oNP R是开放的，尽管这通常被认为是错误的。Muhnik和Vereshhagin[MV96]也提供了关于相对化关系的各种结果分离性和其他命题之间的关系。2定义和分类我们在这里定义了一个在复杂性理论中可能并不广为人知的概念。对于这里没有定义的概念，请查阅形式语言和复杂性理论的文本，如Hop roft和Ullman [HU79]。2.1语言、语言和运算令表示所有长度为nite的二进制字符串的集合，n表示长度恰好为n的字符串的集合。语言和语言是语言的子集。设A是一个Orle，An是A\n，即An是A中长度为n的字符串我们有时会滥用符号，用orale的名字来表示它的意思。哈拉特里什蒂 也就是说，如果x 2 A，则写A（x）= 1，否则写A（x）= 0。4一个方程A是稀疏的，存在一个多项式p，使得对于所有n，jAn j p（n）。两个顶点A和B的连接，记为AB，是顶点fx 0：x 2 Ag[ fx 1： x 2 Bg。我们在这里工作的许多人都会有裂缝。这是通过让tower是从整数到整数的函数来定义的，具有以下递归定义：tower（0）= 2，tower（n + 1）=2tower（n），即， tower（n）是n + 1 2的指数塔。当A（x）= 1时，jxj= tower（n），对于某个n 2！ （Ra ko [Ra 82]使用了一个与此非常相似的概念。我们将所有允许的长度那些长度等于塔（n）对于一些n。修正了一个特殊的多项式时间计算和输入。直观地说，我们让ora les gappy，这样只有在一个允许的长度上的字符串才能被计算。 计算没有足够的时间来查询任何较长长度的字符串，而它有足够的时间来查询所有较短长度的字符串，我们假设它有。设A是一个ora le。 An的零侧是An中以0结尾的字符串的集合。 一边是以1结尾的字符串的集合。我们说An是零空的，如果它不包含以0结尾的字符串，如果它不包含以1结尾的字符串，则它是一空的将输入x固定到一个非确定性的多项式时间的图灵机M。该输入生成M中的计算路径树。与这些路径中的每一个相关联的是查询集：（q; r）形式的对的列表，其中eahq是orle查询，eahr是一位orle响应。我们说一个路径expe ts一个字符串q在一个orle A中，如果（q; 1）在它的查询集中。如果（q; 0）在它的查询集中，则它期望q不在i ti上的两条运算路径，对于某个字符串q，一条在其查询集中具有对（q; 0），另一个是（q; 1）。换句话说，一条路径使q在orle中，另一条路径使q不在orle中。 一个不确定性的计算路径a相对于一个orle Ai以 a epting状态结束，并且对于其查询集中的每个（q;r），q 2 A（） r = 1。一条路是零空i，对于每个以0结尾的q，r = 0。 它是一个空的i，对于每个以1结尾的q，r = 0。2.2语言少女除了众所周知的语言类P，NP，oNP和PSPACE，我们将使用函数类FP和语言类UP，我们在这里定义。一个函数f由一个确定性图灵机M用一个特殊的输出带来计算，如果f（x）= y，并且当M有一个输入字符串x时，在它的输出带上的字符串y停止FP是由多项式时间有界确定性图灵机计算的一类函数。一个函数f2 FP是诚实的，i存在一个多项式p，使得对于所有x，p（jf（x）j）。也就是说，f不将非常长的输入映射到非常短的输出。语言L在UPi中，存在多项式时间有界的不定图灵机M，满足L = L（M），且对任意x，若x2 L，则运算M（x）有一条精确的路径. Grollmann和Selman [GS 88]证明了P6 = UPi单向函数的存在. 单向函数是FP中一对一的诚实函数，其逆函数不在FP中设L0和L1是两个不相交的NP语言或oNP语言，即L0\L1 = ;我们说它们是P-可分的，如果存在一种语言L2 P，使得L0LL1.2.3热内里conditions and ora les我们的大部分单词都是普通单词。这些都是根据某种一般条件来定义的，其定义通常是为了满足一组特定的要求。51Cohen条件是f 0;1g的偏函数，其定义域为nite. 一个条件扩展另一个条件，当对所有的x 2dom（），（x）=（x）. 一个orle A扩展了一个条件时，对于所有x2dom（），A（x）=（十）. 两个条件和当对所有的x2dom（）\dom（），（x）=（x）时，他们不是这样的。非正式地，一组条件S是可定义的，如果它们被描述在一个正式的逻辑模型中，该模型足够强大以表达本文中的任何定义。 形式上我们说一组条件S是可定义的 如果他们坚持到底，使（）true where （）是一个1预测（见罗杰斯[Rog87]）。一组 条件S是稠密i，对于每个Cohen 条件，有一个 条件2S延伸一个Orle满足 S，如果它扩展了S中的至少一个条件。一个科恩将军是一个在每一个密集的，可定义的科恩条件集中，至少满足一个条件条件是gappyi，当（x）= 1时，jxj = tower（n），对于某个n 2！塔的功能如上所述一个大小有界 的 条件是一个对（;k），其中k 2！和是一个缺心眼的科恩条件。 设n为允许的长度。整数k表示任何扩展条件都不能允许长度为n的字符串超过n=2k。因此，一个大小有界条件（;j）扩展了另一个大小有界条件（;k）（（;j）（;k））i和jk，如果x 2 dom（）dom（）则jfy：（y）=1 &jyj=jxjgjxj= 2 j。在其余条件的定义中，设n是一个仅在允许范围内变化的变量，长度AUP条件是一个Cohen条件，它的定义域是gappy的，并且对所有的n，（y）= 1gj1. 也就是说，在一个条件中，最多有一个长度允许的字符串。 一面倒条件是一个Cohen条件，它的域是gappy，并且对所有n，编号：(y0)= 1gj 1.也就是说，它的零侧是UP条件，一侧是Cohen条件。NP\oNP条件 是一个科恩条件，其领域是有间隙的。 此夕h如果对于长度为n的某个字符串z定义，则存在长度为n 1的x，因此，对于所有长度为n 1的y，或者：1.(x0)= 1和 (y1)= 0，或2.(x1)= 1且（y0）= 0。换句话说，允许长度的零端或一端（但永远不会两者都是）是空的。一个NP-P-不可分条件是定义域为有隙的Cohen条件.与NP一样，在某些情况下，如果为长度为n的某个字符串z定义，则零侧或一侧为空。然而，与NP\oNP条件不同，两边都可以是空的。一个UP NP\ oNP条件是一个Cohen条件，它的定义域是gappy和su h，在每个长度n处，如果有一个z2nsu h使得z2dom（），那么1. 二○ ○二年n1（y0）= 1gj1和2.存在一个x 2n2 su h，对于所有y 2n2，或者：（a）（x 0 1）= 1和（y 11）= 0，或者（b）第（1）款(x11)= 1且（y01）= 0。简单地说，这些条件是零侧的UP条件和一侧的NP\oNP条件。对于类型X的每个generi条件，对应的X generi orle是满足X条件的每个稠密的、可定义的集合的一个。6引理2.1对于每一个在上述条件下，存在X-generi ora le。证据一个人认为这个结果纯粹的拓扑的理由，但larity，我们给一个建设性的论点在这里。修复一种条件X。设S1;S2;：是X的稠密可定义集合的枚举条件。“de nable”意味着只有一个可计数的子集。这是我们要求可靠性的唯一原因。让0成为，无处不在的乐趣。对于大小有界的泛型，设0=（; 0）.对于i = 1; 2;：做以下事情：通过Si的密度，在Si中，它扩展了i1。让i=.设G=li mi！1一. G遇到了所有的S，而S是X的代名词。一个相对化语言LX相对于某种类型的生成具有一个性质P，如果对于该类型的所有类G，LG具有P.例如，语言LX= f0n：（9x）jxj = n x 2 Xg在UP范畴上与UP类属G有关，因为G在每个长度上至多包含一个字符串。一个普通的图灵机MX也可以具有一个属性，generi ity的概念。例如，说一台机器相对于Cohen generi ora les在类别上是UP，意味着当相对于Cohen generi ora le进行计算时，机器在每个输入上最多有一个epting路径。在下面的许多证明中，我们使用了这样的说法，即如果一台机器在某种程度上，它拥有某种属性，那么它的权力就受到某种限制。2.4命题Q和Q0现在我们引入两个与NP和oNP中的P-可分性密切相关的概念，它们都是命题Q和Q0。 他们首先被Bor odin和Demers[BD 7 6]研究，并被Fenner，Fortnow，Naik和Rogers [FFNR 96]广泛研究。本文中所提到的结果的推广和证明可在后面的文章中找到命题Q引理2.2（参见[FFNR 96]）以下是等价的：Q1. 对所有的NP机器M，若L（M）=，则存在函数f2FP，若对所有的x2，f（x）是M的一条环路.Q2. 对所有的NP机器M，若L（M）2P，则存在函数f2FP，若对所有的x2L（M），f（x）是M的一条可调路.Q3.对所有的CNF命题公式集S，S SAT和S 2 P，存在函数f2FP，SS，f（“）是”的满意赋值.Q4.对于每一个实到函数f2FP，存在一个函数g 2 FP，使得对所有x，f∈g（x）= x.我们把命题Q定义为引理2.2中任何和所有陈述的真值0号提案引理2.3（参见[FFNR 96]）以下是等价的：1. 全部不相交 oNP集是P-可分的.2. 对于每一个到上的诚实的f2 FP，存在g 2 FP，其范围是并且对于所有x，g（x）是y的第一位，并且f（y）= x。73. 对于每一个上，诚实的f2 FP和每一个常数k和每个p： ！k2 FP，有一个g：！k2 FP则对所有x 2，g（x）= p（y），对y，f（y）= x.4. F或任意两个NP集合L1和L2，若L1[L2=]，则re是一个函数g：！ f 1;2 g 2FP则g（x）=i意味着x2 L i对所有x2.5. F或任意k个NP集L1，：;Lk满足[1ikLi=，re是函数g：！f1;：;k g2FP证明 g（x）= i意味着 x 2 Li对所有 x 2.我们把命题Q0定义为引理2.3中任何和所有陈述的真值。 最后，我们把命题Q和Q0联系在一起推论2.4命题Q蕴涵命题Q 0（因此蕴涵所有不相交的oNP集合都是P-可分的）。Q0是否蕴涵Q是开放的。由于Q蕴涵Q0，我们将使用下面的引理，推论2.4，来证明所有不相交的oNP集合是相对于某些orles的P-可分的。引理2.5假设P = PSPACE并且令S是稀疏环。如果MS是NP S机器，则对所有TS，L（MT）=那么，相对于S，命题Q成立，即， 存在一个函数fS2FPS，使得对所有x，fS（x）是MS（x）的一条可移动的路。证据设f（x）是由图1中的算法定义的函数该算法使用P =PSPACE假设找到了M（x）的一条路径，并使用S来确定何时在S中找到了字符串。我们需要证明算法在多项式时间内正确运行。我们假设，对于所有的TS，L（MT）=，很容易看出L（M）总是在算法中。 如果一个人如果算法找到的路径p在MS（x）中不是一条可接受的路径，则在S中存在某个z，使得（z; 0）在p的查询集中。因为S是稀疏的，所以在算法确定可以查询输入的长度的对象X.但是，while循环终止，因为算法将找到MS（x）的一条有效路径。给定一个输入x，它 在 x 上 有一 条路径。让=;.当存在M（x）的一条顶点p;到计算FS（十）8路p时，如果p是MS（x）的一条顶点路，则输出p和停止其他令z2s是一个由MS（x）9在路径上查询的字符串Let：=[fzg;EndifEndwhile图1：引理2.5中本文中的每一个稀疏环都满足引理2.5的要求。10<0给所有的X。令CX=LX且CX=LX。Ci形成一对不相交的oNPX1012.5oNP中的一对不相交语言我们现在将在oNP中定义一对范畴上不相交的语言，相对于我们使用的某些词，它们将是P-不可分的。 这篇文章简化了Impagliazzo和Naor[IN 8 8]以及Cres enzi和Silvestri [CS 93]的类似结果。我们首先定义以下两个相对化的函数：fX（x）=X（x0jxj11）X（x 0jxj211）：X（x 1jxj）hX（x;y;z）=>8>：0jxj+jyj+jzj如果x;y; z不都是相同的长度fX（x）如果f（y）=f（z））y = zx如果y = z且f（y）=f（z）对于所有的X，fX是长度保持的，并且它在X中依赖的所有字符串都是相同的长度，并且以1结尾。而且，对于所有的X，hX是诚实的。我们还拥有：引理2.6对于所有的orles X，rng h X =.证据这足以表明，对于所有n，nrnghX.固定一个n。案例1.在长度n上，fX是一个置换。因此，对于每个w2n，存在x2n满足fX（x）= w。因此hX（x; 0jxj; 0jxj）= w。案例2. 在长度n上，f X不是置换。 则有y 0; z 02 n，满足y 06= z 0和fX（y 0）= fX（z0）. 因此，对于每个w，hX（w; y0; z0）= w。我们接下来定义以下两种语言：X=fw：（9 x; y; z）hX（x; y; z）= w且x以0 g开头X=fw：（9 x; y; z）hX（x; y; z）= w且x以1g开头因为h是诚实的，我们可以用一个长度为w的多项式来限制x，y和z的长度，所以这些语言都是NPX。 它们的并集包含rnghX，因此，根据引理2.6，它们的并集是相对的0 0 1 1for all ora les X.为了更容易地引用这些语言，这里是它们的解释定义：X=fw：（8x; y; z）hX（x; y; z）= w）x以1g头X=fw：（8x; y; z）hX（x; y; z）= w）x以0g下面的引理总结了命题（P2）到（P5）之间的已知关系引理2.71. 如果oNP中没有P-不可分集，则P = NP\oNP。2. 如果NP中没有P-不可分集，(a) P = NP\ oNP;(b) P =向上。证据第1项和第2a项很容易看到。第2b项的证明见于Grollmann和Selman [GS 88]。LLCC11在这一节的结尾，我们提到，相对于我们构造的所有方程，P6 = NP。 这是真的，因为这些词中的每一个都允许我们使用贝克、吉尔和索尔所使用的同样的对角化来创造NP语言，而不是P语言。123结果在这一部分中，我们假设所有的陈述都是相对于一个词le H suh做出的，PH = PSPACEH。例如，我们可以让H是PSPACE的hara teristi函数-完整的语言量化布尔公式。我们可以做这个假设是因为所有的证明在这一节相对化，也就是说，如果有一个orle相对于其中一个定理的假设是真的，那么这里给出的证明是sudicient建立真理的假设相对于该orle。因此，定理陈述为：设G是一个X-generi 奥拉湖 那么下列命题为真：. . .应解释为：设H是相对于P = PSPACE的一个角。设G是一个关于H的X-广义的欧拉.那么下列命题为真：. . .在四个命题（P2）到（P5）中，有十六种可能的组合，其中一个为真，另一个为假。 如果它在逻辑上是一致的， 我们现在知道的含义。 这留下了八个持续的组合。 我们的假设是表明，对于这八个中的每一个，都有一个与它成立相关的奥拉。 这一点很重要，因为它表明命题（P2）到命题（P5）之间任何尚未知道的关系都需要不相对化的技术。这在表1中进行了总结，表1列出了每种持续的combination，一类generi ora le和一个定理数。设G表示其中一个类。给出的定理证明了相应的组合相对于一个曲面HG成立，其中H如上。为了将类从P中分离出来，我们通常定义一种语言L，它依赖于类的泛型。这就给了我们，对于任何多项式时间决定性的图灵机M，一个无限多的边，以防止M从一个epting L。也就是说，我们有无限多的机会对角化M。为了使一个类等于P，我们证明了对于类中的每一个语言L，一个图灵机算法，一个eptsL和运行在确定的多项式时间相对于一个特定种类的generi ora le。这个算法在某种程度上是我们 通常 算法 的一 个变 体“ 设C = HG ， 其 中 G 是 Cohen generi 。 " 通 常算 法” 是 指Blum 和Impagliazzo[BI 8 7]中用来证明PC=NPC\oNPC且所有不相交的NPC集对都是PC-可分的算法，或者是指Blum和Impagliazzo [BI 8 7]中用来证明PC = UP C的算法以及Hartmanis和Hema handra[HH 87，BI 8 7]中用来证明PC= UP C的算法。定理3.2演示了相对于科恩一般定理的命题会发生什么的其余的定理证明了相对于在各种各样的条件下都是通用的ORA LE发生了什么。在证明这些定理中的每一个定理时，我们将确定产生所需定理的条件。定理3.1设G是一个大小有界的广义元。然后1. PG = UPG;2. PG = NPG\ oNPG;3. 没有PG-不可分集， NPG;4. oNPG中不存在PG-不可分集。13P=起来P=NP\ONP没有NPP-insep没有 ONPP-insep给我THMYYYY大小有限的3.1YYYN科恩3.2YYNYsb-NPP-insep3.4YYNNNPP-insep3.3YNYY一致地{YNYN一致地{YNNY一致地{YNNNNP\oNP3.5NYYY一致地{NYYN一致地{NYNY起来3.6NYNN单侧向上3.7NNYY一致地{NNYN一致地{NNNY一致地{NNNNUPNP\oNP3.8表1：结果证据一个大小有界的广义引理充分证明了引理2.5的假设，所以命题Q对G成立由此和推论2.4，所有不相交的oNPG集对都是PG-可分的.为了证明NPG中不存在PG-不可分集，设M0和M1是一对范畴NP机器，它们的语言在大小有界的条件下是范畴不相交的.设（; k）是一个大小有界的条件。 用条件（; j）扩展它，其中=j= k + 1。 为所有但是，任一机器中的输入路径的数目x必须要求在ORE中不超过j×j=2j个串。 因此，我们可以使用通常的算法，但忽略一条要求G中有多于jxj= 2 j个字符串的路径。算法的工作原理是，如果有一个14如果在M（x）和M（x）中都有一条可移动的路，则这些路一定是可移动的。 如果他们是为了证明oNPG中存在PG-不可分集，设CX和CX为语言，fX为第2.5节中定义的函数。 我们现在证明CG和CG不是PG-可分的. 让成为科恩家族的一员0 1彼此之间，（k） 本可以延长一个 条件（0; k），则e两台机器都是一台电动机。但这违反了ategori al disjointness的假设。由于在NPG中不存在PG-不可分集，所以根据引理2.7，PG= UP G和PG= NP G\oNP G.定理3.2设G是Cohen类奥拉湖然后1. PG = UPG;2. P = NPG\ oNPG;3. 没有PG-不可分集， NPG;4. oNPG中存在PG-不可分集。是的。第一个问题见[BI 8 7]和[HH 87]。 第三种方法与证明PG= NP G\oNP G的方法基本相同。0 10 115001000010在此基础上，我们证明了e L（MG）不是CG和CG的PG-分离子.设M是一个在时间p（jx，j）上运行的多项式时间的行列式。固定一个偶数长度n，p（n）2n. 选择两个长度为n=2的字符串w0和w1在w0上运行M，然后在w1上运行 M，回答 的域中，以允许f在长度n=2的字符串上实现部分置换，该部分置换不将字符串映射到w0或w1。调用生成的扩展名0。 由于M只查询一个多项式数，所以存在一个扩张 字符串。如果Ma epts or reje ts both strings，extend0到a使f成为置换映射a从0到w0开始的字符串，其中h将w0放入C，以及从1到w1开始的字符串，其中h将w1转化为C. 如果Ma epts one and rejes the other，扩展0到a使得f成为一个置换映射两个不同的字符串，都从0开始，到w0和w1，因此对于ing w0; w1 2 C。在任一0 1定理3.3设G是NP-P-不可分的广义元，奥拉湖然后1. PG = UPG;2. PG = NPG\ oNPG;3. NPG中存在PG-不可分集;4. oNPG中存在PG-不可分集。证据我们首先证明了PG = NPG\oNPG.设M0和M1是NPG，则在NP P-不可分的条件下，M0和M1是范畴互补的语言。固定一个输入x，让n是唯一允许的相关长度。 我们将证明一个算法，apts xix 2 L（MG）。如果我们知道G中是否有长度为n的字符串，如果有，它们是否都以0结尾或1，我们可以在此假设下运行通常的算法，并得到orre t结果。由于我们不知道先验，算法必须做一些假设。它首先假设允许长度为空，因此他知道在MG（x）中是否有一条路径P，在orale中没有字符串达到允许的长度。 有两种情况：案例1.有一个P。沿着P到G进行所有查询。如果这些查询没有找到允许长度的字符串，则P是相对于G的有效路径，因此，如果某个查询的结果是一个以0结尾的字符串，那么在orre t假设下运行通常的算法，即在允许的长度下，orre le中的每个字符串都以0结尾。如果找到以1结尾的字符串，也要这样做。案例2.没有sup。那么在MG（x）中一定存在一条路径P0，它在给定长度的环中不存在字符串。如果不存在，则机器都将被强制通过在允许的长度处没有字符串的orle来reje t x，这违反了它们的范畴互补性。沿着P0到G进行所有查询。如果P0确实是一条有效路径，则拒绝。如果它不是一个a epting路径，那么如上所述，算法在G中以允许的长度创建一个字符串，并使用它在orre t假设下运行通常的算法。接下来我们证明PG = UPG。 设M是一台机器，它在类别上是UP，NP P-不可分条件 固定输入x。 运行通常的算法，假设允许的长度是1-空的，即在MG（x）中只允许有1条空的插入路。如果找到一个epting路径，一个ept。 如果不是，而不是直接拒绝，再次运行通常的算法，但这一次假设允许的长度是零空，所以只考虑零空的路径。 如果找到一个请求路径，则请求，否则拒绝。 这是因为允许16我01010n1 &yi2X g，其中i2 f0;1g. 相对于G，LG和LG是一对不相交的NPG集. 让be不管怎样我们 e L（M）不是LG和LG的PG-分隔符。多项式时间决定论 ora le machine hine不是CG和CG的PG-分隔符。其次证明了NPG中存在一对PG-不可分集.设LX和LX是语言在定理3.3中定义我们可以用这里的论证来证明LG和LG在NPG中，长度是零空或一空，所以如果MG（x）有一个epting路径，它将是零空或一空。现在我们证明在NPG中存在一对PG-不可分的语言. 令LX= f0 n：（9y）[jyj =0 1设M是在时间p（j × j）上运行的机器的决定性多项式时间。 设n是一个允许的长度，h在其上小于ned，且p（n）2n 1。 设m是允许长度，其中m> n，小于长度m，且p（m）2m-1。运行计算M（0n）。让是…的延伸对于未被查询的字符串，设置了计算，使得0 n在L中。有两种情况：案例1.这是一个epts。运行计算M（0m）。如果是epts，则扩展到条件 通过设置长度为m的未查询字符串，使得0m在L中。如果它不允许，就把它们设置成0m在L中。案例2.结果不合格。运行计算M（0m）。如果是epts，则扩展到条件所以0m在L0中。 如果不允许，则将它们设置为0m位于L1中.0 1最后，我们证明了在这类语言中存在P-G-不可分的语言。oNPG. 令CX CX 是语言和fX第2.5节中定义的函数fX的定义允许我们使用与定理3.2相同的条件，将一个NP P-不可分条件推广为另一个，0 1定理3.4设G是一个大小有界的NP-P-不可分广义子空间。然后1. PG = UPG;2. PG = NPG\ oNPG;3. NPG中存在PG-不可分集;4. oNPG中不存在PG-不可分集。证据首先证明了oNPG中不存在PG-不可分集. 由于一个大小有限的泛型，在引理2.5的假设下，命题Q对G成立，所以由推论2.4，所有不相交的oNP G集对都是PG-可分的。由此和引理2.7，P G = NP G\oNP G。0 10 1PG-密不可分。最后证明了PG= UPG.设M是一个NP机器，它在大小有界的NP P-不可分条件下是UP的.设（;k）是一个大小有界的条件。用条件（;j）扩展它，其中=且j = k + 1。对于除了nite数目的x之外的所有x，MG（x）中的一条遍历路径必须要求在该orle中不超过jxj= 2 j个字符串。 因此，我们可以使用通常的算法，但忽略一条要求G中有多于jxj= 2 j个字符串的路径。 该算法的原理是，如果M（x）中存在两条连续的路，则这两条路必在M（x）中。 如果它们彼 此 相容，（;k）将被扩展一个条件（0; k），这将使e M（x）有两个epting路径，违反了假设，它是 分类上。定理3.5设G是NP\oNP-广义子空间. 然后1. PG = UPG;1700101oNP X. 根据G的定义，LG= LG所以LG2NPG\oNP G. 设为NP\oNP条件2. PG 6= NPG\ oNPG;3. NPG中存在PG4. oNPG中存在PG-不可分集。Homer和Selman[HS 9 2]创造了一个使定理3.5的推论为真的定理。 我们将给出一个简单的证明使用泛型。定理3.5的证明由于G中的一个允许长度是零空或一空，我们可以用与定理3.3完全相同的方法证明PG= UPG其次，我们证明PG6=NPG1oNPG. 设LX=f0n：（9y）[jyj= n1 y02X g，X=f 0 n：（8y）[jyj=n1）y 1 2=X g. LX属于NPX和LX是 类别盟友在0 1 0并且M是在时间p（j × j）上运行的机器的多项式时间的确定性。设n是一个允许的长度，并证明p（n）2n 1。在输入0n上运行M。有一个长度为n的以0结尾的字符串x没有被M（0n）查询，而一个长度为n的以1结尾的字符串y没有被查询。如果M a ∈ 0n，令被[fyg.如果M请求为0n，则令被[fxg.在这两种情况下，设x或y为只有长度为n的字符串。 我们知道M（0n）a ∈i0 n2=L.在NPG和NP G中都有PG-不可分的集合对，oNPG由引理2.7得出定理3.6设G是UP-广义的，奥拉湖然后1. PG 6= UPG;2. PG = NPG\ oNPG;3. NP中存在PG-不可分集;4. oNPG中不存在PG-不可分集。是的。 首先证明PG6=UPG. 设LX= f0 n：（9 y）[jyj=&ny2X g. 根据G的定义，LG2 UP G.设是UP-条件，M是在时间p（j × j）上运行的行列式多项式时间的机器。设n是一个长度，h在其上未定义，且p（n）2n成立. 在输入0n上运行M，对长度为n的字符串的任何查询响应0将有一些长度为n的x未被查询。如果M是个epts，则设是，所有长度为n的字符串都被忽略。如果M不同意，那就随他去吧[fx g，其中省略了其他长度为n的字符串。然后我们证明M（0n）a ∈i0 n2=L.根据引理2.7，在NPG中存在一对PG-不可分集.引理2.5的假设对UP-亏格成立， 所以命题Q对G成立。通过推论2.4，所有不相交的oNP G集对都是PG-可分的。 根据引理2.7，P G= NP G\oNP G。定理3.7设G是单侧UP-广义的，奥拉湖然后1. PG 6= UPG;2. PG = NPG\ oNPG;3. NPG中存在PGL184. oNPG中存在PG-不可分集。190000111000如前所述，G是有间隙的，因此至多一个允许的长度是计算MG（x）和MG（x）。1M（x）则P必在MG（x）中。 转到步骤MG（x）.设M0G（x）是除去零侧有一个字符串的任意一条路径的MG（x）.在没有任何假设的情况下，对M 0（x）和M（x）运行通常的算法，扩展 从步骤1. M（x）中的每一条路径都必须与M 0（x）中的P一致，所以，像往常一样，a需要琴P在M0G（x）中（并且当eMG（x））和在MG（x）中存在一条至多为1的epting路P1清空M0（x）中的一个epting路径。 如果是这样的话，a ept是ause M 0G（x），所以M G（x），证据首先我们证明P G = NP G\oNP G。设M0和M1是NPG-机器，它们的语言在单侧UP-生成条件下范畴互补.固定输入x。我们将证明以下多项式时间算法apts xix 2 L（M G）。0 1该算法可以忽略零侧上的任何在环中存在多于一个字符串的epting路径。如果在允许长度的零侧有一个字符串，并且算法发现了它，我们可以使用这个信息运行通常的算法并得到一个正确的答案。设是其在G中的成员或非成员已经确定的字符串的集合。初始化到;。步骤1.在这一步中，我们试图确定哪一个机器有一个零空的运行路径P，与允许长度的一侧兼容。P必须存在。如果不是，则两种机器中的每条路径在允许长度的零侧的orle中至少有一个字符串。那么两台机器都应该通过使零侧为空来reje t x。但这违背了语言在类别上是互补的假设。在允许长度的零侧为空的假设下运行通常的算法即在M（x）中只考虑零-空的一条边路。 如果在MG（x）中存在一条零-空顶点路，算法将在多项式时间内找到它如果我们用完了零空的一个ep