实数模型中的概率可检查的证明：NP类的新表征与组合优化问题的连接

理论计算机科学电子笔记123（2005）165-177www.elsevier.com/locate/entcs关于实数的Klaus Meer克劳斯·梅尔1，2数学与计算机科学系Syddansk Universitet，Campusvej 55，5230 Odense M，Denmark摘要概率可检验证明（PCPs）在复杂性理论中具有重要的意义一方面，他们提供了一个新的表征的复杂性类NP，另一方面，他们显示了深刻的连接到组合优化问题的近似结果。本文研究Blum，Shub和Smale的实数模型中PCPs的概念。讨论了NP的实数类比NP R的透明长证明的存在性。保留字：PCP，实数模型，在实数上进行自我测试。1介绍在过去的十年中，理论计算机科学中最重要和最具启发性的结果之一是Arora等人在1992年证明的PCP定理，[1，2]。在这里，PCP代表概率可检查的证明，这个概念在20世纪80年代末的交互式证明中得到了进一步的发展。PCP定理用被某些所谓的验证器（veri fier）所接受的语言来描述NP类，这是概率图灵机的一个特殊版本。它允许稳定问题的验证程序在NP中，在以下意义上。 假设对于一个问题L∈NP和一个问题1部分由欧盟PASCAL模式分析、统计建模和计算学习卓越网络和丹麦自然科学研究委员会SNF支持2电子邮件：meer@imada.sdu.dk1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.04.047166K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）165/∈/∈⊆实例x∈{0，1}我们不需要在多项式大小的顶点y∈{0，1}为x∈L的情况下进行计算。那么很有可能（除非P = NP）我们必须读过y的所有分量，然后才能决定y是否证明x∈L。PCP定理背后的稳定化思想要求使用具有以下性质的不同证明：如果x L，则所有证明通过仅检查校样中的一定量的成分，将以高概率被拒绝。令人惊讶的结果是，上述术语PCP定理本身已经引起了极大它被用来显示几个（非）近似性结果之前不知道。关于PCP定理的介绍和证明，请参见[3，12]。Blum、Shub和Smale在1989年将结构复杂性理论推广到有限字母表上，并统一了代数复杂性理论中的现有方法，引入了一种统一的实数计算模型，现在称为BSS机[6]。同时，在盲源分离模型方面也做了大量的工作。教科书[7，5，4]阐明了在这个框架中考虑的问题。然而，到目前为止，对于BSS模型，既没有PCP结果，也没有适合于经典近似的实数近似概念3（然而，在[13]中考虑了交互式证明由于图灵模型中PCP结果的重要性，这样这里，将描述这样的尝试。请注意，PCP定理中提出的原始问题在真实框架中也是完全有意义的：我们可以有一个NPR问题的验证程序L<$R<$：=∞Rnn=1使得在X情况下L对于任何潜在的证据y只有不断地许多真正的为了以高概率拒绝，必须检查y的分量？我们引入真实的验证器以及真实的PCPR类。然后，它表明如何稳定的验证证明NPR-完全问题可以构造。更准确地说，我们设计透明的（即，指数地）长的证明，其仅使用这将显示NP RPCP R（poly，O（1））。在最后一节中，我们简要地概述了实数上近似问题的关系。大部分细节可以在[11]中找到。[3]在这里，我们不考虑数值分析中处理的近似问题这种概念可能会导致原始BSS模型中的问题，除非引入解析函数，参见[8]和[10]。因此，一个更组合的概念似乎是合适的。K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）165167联系我们2问题设置2.1二次多项式系统在R上的BSS模型中，实数被认为是实体。基本的算术运算+，−，，：可以以单位成本执行，并且有一个测试运算反映了实数的潜在排序决策问题现在是子集L<$R<$：=∞n=1 R n. 代数（Algebraic）n是n。在固定了这些概念之后，就很容易定义P和NP类的实类似物PR和NPR以及NPR的概念。等网站和资源有关BSS模型的更多详细信息，请参阅[5]。例2.1（二次多项式系统）让我们考虑实数上的一个典型决策问题。QPS（Quadratic Polynomial Systems，二次多项式系统）决策问题如下：输入：整数n，m∈ N，系统p：=（p1，.，p m）的实多项式在n个变量中，每个变量的次数最多为2;此外，每个pi最多取决于3个变量。问题：是否存在公共实解a∈Rn使得p（a）= 0∈Rm？在不损失一般性的情况下，我们可以假设m=O（n）（通过添加虚拟变量）。QPS问题是NPR-完全的.让我们在这里只是表明为什么它是在NP R：对于一个输入n，m，p1，.，p m，我们猜测a y ∈Rn，pi（y）对于所有的i和接受i，则所有结果消失。 不难看出，这是一个真实的故事。阳离子程序需要多项式（代数）运行时间在（代数）输入大小，只有。这是QPS问题，我们稍后将为它构造一个实数验证器。2.2验证者和经典PCP定理在本节中，我们首先简要回顾用于陈述经典PCP定理的基本概念。考虑输入Φ（x1，...，对于NP完全3-SAT决策问题，“自然”NP验证是通过猜测赋值y 0，1 n，将其插入Φ并检查Φ（y）= 1来给出的。显然，除非P = NP，否则该过程通常需要检查y的所有分量以得到正确答案。这同样适用于上述“自然”验证程序，表明QPS属于NP R。现在PCP定理背后的思想是表明存在其他更稳定的验证程序，因为只需检查常数数量的证明组件。为此付出的代价是，不属于所考虑的语言的输入可能会被接受，168K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）165ρ›→--∗--ρ2确定的，虽然很小，概率（回忆一下，在NP的定义中，错误的验证总是被拒绝的）。从形式上讲，这个想法是通过引入验证者的概念来实现的。定义2.2a）设r，q：N N是两个函数。图灵模型中的（r（n），q（n））-限制验证器V是一个特殊的随机图灵机，它有几个流。对于一个输入x∈{0，1}，如果x ∈ { 0，1 }是siz en，0、 1个 用某种语言表示x的潜在成员资格证明验证器首先产生r（n）个随机比特的序列（在0，1 r（n）上的均匀分布下）。给定x和这些r（n）许多随机比特，V在n中的确定性多项式时间内计算q（n）的索引，y的许多分量。最后，V使用输入x以及选择y的分量，以便执行确定性多项式时间算法。在这个算法的最后，V要么接受要么拒绝（x，y）。我们用V（x，y，ρ）表示V的结果，假设为输入（x，y）生成的随机序列是ρ。b）部分a）几乎可以逐字修改，以定义核查人员对于BSS模型。随机部分将是一个实数算法，抛硬币。 输入x和验证y现在属于R。 的x的位长度被其代数大小替换。注2.3i）重要的是要注意，实数验证器定义中使用的概率概念仍然是指离散样本空间及其均匀分布。ii）随机化依赖于掷硬币的概率BSS机在[9]中进行了研究。其中示出了BPPR= PR 我们的结果实际上给出了模拟BPP-R计算的确定性算法的某些下界信息（如果PRf = NPR）。验证器现在用于定义PCP-和PCPR-复杂性类。因为后者是新引入的，所以这里我们只给出实类的定义图灵框架中的PCP类的定义类似于将BSS设置中的明显项再次替换为图灵模型中的明显项。定义2.4设r，q：N <$→ N;一个实数决策问题L<$R <$在类PCPR（r（n），q（n））i中，如果存在（r（n），q（n））-限制验证者V，使得下面的条件i）和ii）成立：i) 对所有的x∈L，有一个y∈R，使得对所有随机生成的字符串，ρ∈ {0，1}r（sizeR（x））验证者接受：Pr {V（x，y，ρ）= JacceptJ}=1。ii) 对任意的x/∈L和y∈R∈ R，有Pr{V（x，y，ρ）=JrejectJ}≥ 1。K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）16516922概率在所有字符串ρ∈ {0，1}r（大小R（x））上均匀选择。例2.5很容易看出NP = PCP（0，poly），NP R= PCP R（0，poly）以及PCP（O（log n），O（1））≠ NP，PCP R（O（log n），O（1））≠ NP R。在图灵设置中尝试自己证明P = PCP（O（logn），2）。BSS模型中的模拟语句是什么PCP定理给出了NP的以下令人惊讶的特征：定理2.6（PCP定理，[1，2]）NP = PCP（O（log n），O（1））.证明上述定理的第一步是证明NP有透明的长证明，即NP ≠ PCP（poly，O（1））。一些用于证明完整PCP定理的重要技术在这里已经发挥了作用。后者是Z n上线性函数的所谓自检验和自校正。在真正的框架中，这些技术必须推广到非常不同的领域。3NPR的透明长证明我们的主要结果建立了NP R的透明长证明的存在性。正式地说定理3.1 NP R≠ PCP R（poly，O（1））.“透明证明”指的是这样一个事实，即只有验证证明的许多组成部分必须经常被检查。‘Long proofs’ reflects that when producing a polynomialnumber of random bits there are expo- nentially原则上可以检查的部件。相应的状态NP≠ PCP（poly，O（1））是证明Zn上PCP定理的第一个主要成分，见[1]中的定理5. 因此，我们可以希望建立一个好以下时间复杂度为O（logn），O（1）.3.1新挑战从何而来由于多项式时间约简可以包含在验证器的计算中，为了证明定理3.1，证明NPR-完全QPS问题允许（poly，O（1））-验证器是足够的。要解决的主要问题是找出QPS的稳定验证证明应该是什么样子。由于3-SAT问题的算术化是经典PCP定理的一个主要组成部分，遵循类似的方法是很自然的这种方法取代了170K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）16522222--2XP（y，r2我222由它生成的某些线性（后来是多项式）函数的满意分配。然后，函数值的表替换赋值本身。这种验证的稳定性是通过随机检查内部一致性（即表确实表示线性函数，这些函数都是由一次赋值产生的）和可解性（即赋值是令人满意的）来暗示的。然而，出现了两个严重的困难。首先，经典证明中几乎所有的概率状态都依赖于Z n在加法下的封闭性和Z n上均匀分布的加性移位不变性.这意味着对于固定的a，b∈Zn，我们有Pr{x = b}= Pr {a + x = b}。x∈Znx ∈Zn其次，在Z n上，除了0，1之外，没有其他常数存在。因此，Zn上的线性度等价于以下条件：f（x+ y）=f（x）+f（y）.一旦实数开始起作用，这两个条件都被违反了。由于我们不能将函数表扩大到Rn ，所以要解决的第一个主要问题是：什么是正确的域X<$Rn，我们应该在其上猜测验证过程中的函数值。这个域X必须是有限的，并且必须涉及具体问题实例中存在的实数。在这样的域X上的均匀分布通常既不是移位不变的，也不是在加法移位下闭合的。这个问题变得更糟的事实，现在还需要考虑实数标量因子。同样，从实数的哪些有限集合中取这些标量因子并不明显。 鲁宾菲尔德和苏丹[14]已经处理了关于所谓的理性域的相关问题，这些域是Q的某些结构良好的子集。 我们将展示如何这样的想法可以推广到那些子集的真正出现在有关NP R-完全问题。3.2与QPS考虑QPS的一个实例。对于实多项式p1，...，p mover n variables定义M2r=（r1， . . ，r<$m）∈Zm.（一）i=1当y∈Rn，r∈Zm时，P（y，r∈）≥0;当m∈Z m时，P（a，r∈）=0K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）16517122∈Zm222ai·xi<$x∈R222Σ2ΣΣ Σ ΣΣ Σr∈Zm仅当a∈Rn是一个公共零，否则dr<$Pr{P（a，r<$）>0} ≥1.（二）2P的结构对于下面的内容是最重要的。很容易看出，这种结构可以分成两个不同的部分，一个只取决于输入多项式p i的实系数，另一个取决于变量y的赋值a∈Rn。我们有引理3.2线性函数A，B，C，D只依赖于a∈Rn，以及线性函数LA当然，这样，，...，LD，E：Zm<$→Rn，Rn2，Rn3，Rn4，R，respec-<$r <$∈ZmP（a，r<$）=E（r<$） +A<$LA（r<$） +. . +DLD（r）.更准确地说，nni=12B：Rn2n›→R，B（y1，.，y n2）=n ai aj·yijy∈Rni=1j =1（其中我们用yij表示自变量（i−1）n+j）;C：Rn3n n›→ R，C（z1，.，z n3）=nai ajak·zijk<$z∈Rni=1j =1k =1（其中zijk表示自变量（i−1）n2+（j−1）n+k）;D：Rn4n n›→ R，D（w1，.，w n4）=乌恩ai aj ak al·wijkl<$w∈Rni=1j =1k =1l =1（其中w ijkl表示自变量（i − 1）n3+（j − 1）n2+（k − 1）n +l）。而函数A，...，D也发生在图灵设置中，L A，. D是新的。它们的存在产生了大多数问题，因为对r∈Zm的评估给出了依赖于ctual输入（即其实系数）的rea l向量。因此，A，.，D必须在实数域上计算。这就需要开发新的线性函数自检测和自校正技术.一个自然的第一次尝试正确的实域上测试的线性，比如说，A是L A（Z m）。然而，一般来说，当选择x，y∈LA（Zm）时，元素x+y将不再属于这个集合（由于对于r，t∈Zmwenowwhichhavevtoocomputer+toverRminsteadofZm）. 我们，我们的想法A：R›→ R，A（x1，.，xn）=;34172K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）1652∈2∈2X.Σ222最终导致无限集合，这些集合不能用作猜测函数值的域。相反，我们扩展了Rubinfeld和Sudan [14]为所谓的理性域开发的想法我们的扩展适用于R上更大量的有限子集，并覆盖了可能以上述方式由QPS实例生成的所有潜在域。必须考虑的第二个问题是线性不再仅仅等同于加和性条件。可能的情况是，LA（Zm）分裂成几个分量，这些分量不会通过加法移位而彼此产生。然后，即使A在所考虑的域上满足可加性，我们也必须排除A对应于不同线性函数的情况，每个分量上有一个。因此，必须执行另一个检查标量乘法性的测试。在这里，问题再次是我们必须从哪个域中选择标量。验证器的工作原理如下：(i) 作为猜测，验证器在适当的域上使用A、B、C、D的函数表。这些表将具有输入大小的指数大小。(ii) 检查所有函数是否具有高概率线性。(iii) 检查所有的函数都有很高的概率来自同一个向量aRn。(iv) 对于随机计数器，通过查询函数表来计算P（a，r）的值;检查结果是否为0。4证明细节在本节中，我们收集必要的数学细节来证明主要结果。在[11]中可以找到完整的证据。4.1测试可加性首先，让我们来看看地图A。对于线性映射L A：Z m<$→Rn，设C0：={λ1，.，λ K}<$R是L A的矩阵表示中所有元素的多集，不失一般性λ1：= 1，K=O（n）. 集合0是域我们希望保证A的可加性具有很高的概率。定义为X0：=Ki=1ns i·λ i|s i∈{0，1}，其中1 ≤ i ≤K⊂R n.（三）注意，以下包含项成立：Zn<$X0，LA（Zm）<$X0和所有对于λ∈C0，z ∈ Zn，≤K项λ · z的和属于X0. 示ΣK. Meer/Electronic Notes in Theoretical Computer Science 123（2005）165173δ1一一我δ22/X33n.ΣC1=i=1λti，ti∈{− n，.，n}（五）之前，为了成功地执行自测试，我们考虑在大得多的集合上的A的值的函数这一套定义的手段，X2：=Ki=1s i·λ i|s i∈ {− n，−nn+1，...，n}，其中1 ≤i≤K你好（四）用于证明A在X 0上的线性的验证证明以X2<$X2<$X2的元素上的A值的表格给出。[4]重要的是要注意，使用X2“稳定”了验证过程，因为它比X 0大得多。 这导致X2在来自X0的元素的加法移位下几 乎 不 变 ：Lemma4. 1<$x∈X0是|x+X2X2|对于常数c>0，≥ 1 − c。|n|n验证员进行第一次测试测试1：选择0 <δ<11。对于i = 1到k：=[2|做i) 从X2中随机选取元素x，y;ii) 如果A（x+y）/=A（x）+A（y）拒绝。如果所有测试对都满足加和性，则接受A。命题4.2如果A通过了检验1，那么A很有可能接近（在某种程度上，将g+（a）定义为A（a+x）−A（x）， x∈X2中的多数结果）满足n X 0的可加性的函数g+。4.2标量乘法与上面类似，我们将C0放大为给定的集合C1，.KC1对于λ∈C0的标量乘法几乎不变：Lemma4. 3<$λ∈C0，|λ·C1|≥1−1。下一个测试是|n|n测试2：假设δ2> 0是固定的。 对于i = 1到k：=[2|做i) 选取随机元μ∈C1，x∈Zn;ii) 如果A（μ·x）=A（x），则拒绝。µ4虽然这里没有使用1，但它是在[11]的证明中。因此，我们倾向于不改变符号。3Σ174K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）16582⊗222一如果所有测试元组都满足相等性，则接受A。命题4.4设0 <δ2<1。对于足够大的n，a) 如果A通过关于δ2的测试2而没有拒绝，则存在一个集合M<$Zn，包含Rn的基和满足标量的函数g<$从C0和值x∈ M的标量的乘法性，使得具有高概率A等于A的概率（在类似但更复杂的意义上，以上）。b) 假设测试1和测试2对A进行了无拒绝。若A是关于X 0（关于可加性）和关于C0× M（关于可加性）的线性函数，乘法性），则等式g+和g+和b+是相同的A AR n上的线性函数 我们用g A表示后者;对于g B，g C和gD，分别。验证员对B、C、D（在适当的区域）进行类似的测试。在验证程序的这一点上，我们知道，通过对某些函数值进行多次检查，四个函数表中关于线性的不一致性以高概率（任意接近1）实现。4.3自我纠正、一致性、可解决性它仍然需要检查函数A，.，D都是由单个指派a∈Rn以及后者是否为零而得到的.由于P（a，r）的特定表示，我们使用了可以以类似于在Z 2上进行的小变化执行的新的并行步骤的方法。在第三个测试块中，我们比较函数对（A，B）、（A，C）和（A，D），以确定它们是否来自相同的赋值a。这是通过以通常的方式自校正这些函数来完成的。 比如说，2检查g A：R n <$→ R和g B：R n›→R的结果来自相同的awe检 查 随 机 选 择 的 点 x ， xJ∈ Zn 是 否 g A （ x ） ·g A （ xJ ） = g B （ x<$xJ），其中xxJ：=（x1xJ1，x1xJ2， . . ，xnxJn）对应于在B的定义中使用的变量向量y的适当赋值，参见引理3.2.使用自校正以确保以高概率计算gA和gB定义4.5随机函数SC-A定义如下：对于x∈Zn（注意Zn<$X0）随机选取一个y∈ X2，并返回值A（x + y）−A（y）。对于SC-B也是如此。测试3（一致性）：设0 <δ <1为固定值。 对于i = 1至k：=[log δ4|4log7做8K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）16517522原木1Σ2Σ Σi) 随机选取x，XJ∈ Zn。ii) 根据X2上的均匀分布选取y，YJ，YJJ∈ X2.iii) 如果SC-A（x）·SC-A（xJ）SC-B（x<$xJ）拒绝.如果所有测试点均满足相等性，则接受。命题4.6假设A和B通过了测试1和2;进一步假设相应的线性函数gA：Rn<$→R源于一个向量a=（a1，...，a n）∈RnnA（x）=ai·xi和相应的gB：Rn<$→i=1R源自向量b =（b11，.，b nn）∈rn2n通过gB（y）=nbij· yij.i=1j =1如果a ≤ a/= b，则测试3以至少1 − δ4的概率拒绝。最后，检查a∈Rn是否为零根据（2）完成检验4（满足性）：对于i = 1至k：=[log δ5|做i) 根据Z m上的均匀分布，pic k r∈Zm是随机的。2 2ii) 评估P（a，r）;如果结果不同于从0个对象。如果P（a，r）对所有的t点都是零，则P（a，r）是零。证据（主要定理3.1）所有上述测试应用于所有函数A，.，D为适当选择的所涉及的概率值。如果其中一个测试给出了矛盾，验证者拒绝。如果所有测试均通过且无矛盾，则接受。很明显，如果输入是QPS的可解实例，并且如果猜测的函数表来自公共零，则没有测试会失败。验证者接受概率为1。相反，如果给定的QPS实例没有公共根，则在其中一个测试中检查的条件之一很可能被违反。这将通过不断检查所涉及的函数表的许多值来实现。这些表的大小是指数级的。Q5结论显然，在BSS模型中证明经典PCP定理的完整版本是未来最有趣的问题，即证明（或反驳）时间复杂度为O（logn），O（1）.另一个有趣的话题是与近似问题的关系。 在这里，我们考虑一种半组合近似。注意，在组合逼近的典型设置中，176K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）165∈一个问题实例（如TSP问题的Hamilton循环）是有限的。它们中的每一个都给出了目标函数的值，任务是通过多项式时间算法尽可能地近似最优解。真实世界的情形是不同的，因为我们不能再要求可行解的集合是有限的。通常，我们还必须注意最优解的存在性问题。一个典型的优化问题，我们不认为是适当的，在这样一个框架将计算多项式系统的最小范数解。我们认为与近似问题和实际PCP有关的一个典型问题是：定义5.1 MAX-QPS优化问题定义如下：给定实例n，m∈ N，p1，.，pm，求出了p i中通过赋值y ∈ Rn可同时为零的多项式的最大个数。在这里，可行解的集合可能是无限的，但目标函数的最优值确实存在。考虑到这一点和其他一些方面（比如不需要近似算法来计算可行解，但只保证存在某种质量的解），我们可以定义近似类的实版本，如APX R，PTAS R，FPTAS R。例如，可以显示定理5.2假设猜想NPR= PCP R（O（log n），O（1））成立.在BSS模型中，如果PR = NP R，则MAX QPS不存在完全多项式时间近似方案（FPTAS R）.Q一个更有趣的问题是w.r.t.上述猜想是最大电路接受问题MAX-q-CAP。这里，作为输入，我们考虑n，m∈ N和m个代数回路C1，…、Cm.每个电路具有由索引i1，.，i q∈{1，.，n}。可能存在由实常数标记的附加输入节点。每个电路计算结果“接受”或“拒绝”。然后问题是计算同时接受输入y ∈Rn的电路的最大数量（其中对于y∈ Rn，电路将相应的分量yi1，...作为其q个输入）。 ，y iq）。注意，当q ≥ 3时，MAX-q-CAP是NP R-难的. . 这样就可以证明定理5.3设qN为常数。 则NP R= PCP R（O（log n），q）i，其中存在从QPS到MAX-q-CAP的多项式时间BSS约简Φ，并且Φ> 0，使得- 如果多项式系统p：=（p1，.，p，m）具有公共零点，所有电路Φ（p）同时满足，K. Meer/Electronic Notes in Theoretical Computer Science 123（2005）1651771+1- 如果p最多没有公共零点1Φ（p）中的许多电路可以是同时满足。该定理是关于MAX-3-SAT的一个众所周知的类似陈述的实数版本。然而，目前还不清楚它是否也适用于“更自然”的这些结果的讨论和证明被推迟到未来的文件。引用[1] S.阿罗拉角隆德河，巴西-地Motwani，M.苏丹，M. Szegedy：Proof Verification and Hardness ofApproximation Problems 。 Proc.33rd Annual IEEE Symposium on Foundations of ComputerScience，IEEE Computer Society，14[2] S. 阿罗拉，S.Safra：Probably checking proofs：A new characterization of NP。 Journal ofthe ACM 45，70-122，1998.第33届IEEE计算机科学基础研讨会论文集，1992年2[3] Ausiello，G.，Crescenzi，P.， Gambosi，G.， Kann，V.， Marchetti-Spaccamela，A.，Protasi，M.：复杂性与逼近：组合优化问题及其逼近性质。Springer（1999）.[4] S.巴苏河，巴西-地Pollack，M.F.罗伊：实代数几何中的算法。数学中的算法和计算第10卷。Springer，2003年。[5] L. Blum，F. Cucker，M. Shub，S. Smale：Complexity and Real Computation。Springer，1998年。[6] L.布卢姆，M。Shub，S. Smale：关于实数的计算和复杂性理论：NP完全性，递归函数和通用机器。布尔美国数学学会，第21卷，1[7] P. Bürgisser，M. M. A. Shokrollahi：Algebrai cComplexityTheory，第315卷，格伦达伦Springer，1997年。[8] T. Chadzelek湾霍茨：分析机器。理论上Comput. 科学，219（1[9] F. Cucker，M. Karpinski，P. Koiran，T. Lickteig，K.维特：在真正的扔硬币的图灵机上。Proc.27th STOC，335[10] J. Makowsky，K. Meer：关于Blum，Shub和Smale计算模型中图属性的组合和Meta生成函数的复杂性。In：Proceedings CSL 2000; Peter G.Clote和Helmut Schwichtenberg（编辑），SpringerLNCS 1862，399[11] K.透明的长证明：NP R的第一个PCP定理。扩展摘要将出现在：第31届自动机，语言和编程ICALP国际学术讨论会2004年，图尔库，施普林格LNCS。[12] D. H.J . H. Pr？omel，A. 注：Probabilisticallych eckab e p r o a bleproos和hercon e n cencesforapproximation algorithms。离散数学136，175[13] S. Ivanov，M.de Rougemont：Interactive Protocols on the reals.计算复杂性8，330[14] R. Rubinfeld，M. Sudan：在有理域上有效地自测试多项式函数。Proceedings of the ThirdAnnual ACM-SIAM Symposium on Discrete Algorithms（Orlando，FL，1992），ACM，23