非图灵计算模型及其复杂性理论研究：一个拓展的框架

理论计算机科学电子笔记270（1）（2011）17-28www.elsevier.com/locate/entcs非图灵计算模型什么，为什么和如何Ed Blakey埃德·布莱基1，2牛津大学计算实验室，Wolfson Building，Parks Road，牛津，英国，OX1 3QD，摘要通过解释，我们初步概括了复杂性和非图灵计算的含义我们的标题是基于一个激励性例子的调查，我们认为，传统的复杂性理论并不能充分捕捉某些非图灵计算机的真实复杂性，因此，需要该理论来适应这种机器。我们提出了一个复杂性框架，它不依赖于计算模型，而是可扩展的，以适应不同的计算模型，并允许有意义的比较计算机或者计算机不是不同计算模型的实例。虽然，我们认为，复杂性理论在没有任何修改的情况下对某些非标准模型的适用性有限，但我们希望这里描述的想法能够在某种程度上展示如何进行这种修改，并且非图灵计算社区的成员-尤其是量子物理和逻辑/计算模型发展2008的参与者-发现这些想法既有用又有趣。关键词：计算复杂性，非标准/非图灵计算模型，精度。这项工作是作者正在进行的博士学位研究的一部分。这个项目的更完整的描述 可 以 在 [3] 中 找 到 ， 可 以 在 www.example.com 上 找 到http://users.ox.ac.uk/~quee1871/transfer.pdf。1怎么着. ....复杂性和非图灵计算是什么意思1我们感谢BobCoecke和JoéelOuaknine（牛津大学）的 支 持、 支持和 建议;感谢 Samson Abramsky和 PeterJeavons（牛津大学）对本项目的有益评论;感谢Viv Kendon和同事（利兹大学）对本工作在量子计算中的应用进行的有益讨论;感谢Jonathan Mills（美国印第安纳州）、Susan Stepney（纽约州）和其他人在2007年非传统计算会议上提出的意见和建议;感谢第二届自然计算国际研讨会的与会者令人鼓舞的反馈和讨论。2电子邮件：edward. queens.ox.ac.uk1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.01.00318E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）在本节中，我们简要回顾了计算复杂性的含义，并注意到这个概念然而，我们也注意到，其他模型的广泛讨论和实际使用，并询问是否需要更多的复杂性理论，以允许适当的分析非标准计算机。1.1复杂性计算复杂性领域致力于根据解决方案的成本对问题进行分类。这个成本是在计算过程中消耗的资源（运行时间，内存空间或类似的）;复杂性理论家特别感兴趣的是随着计算输入的增加而增加的资源因此，复杂性理论的概念得到了很好的定义，该领域在很大程度上是相对于一个特定的计算模型而发展起来的：图灵机。这种选择很少被认为是有问题的：绝大多数实际计算都符合这个模型（具体地说，现实世界的计算通常是由运行实现算法的程序的数字计算机执行的）;对图灵机的几乎排他性的考虑得到了进一步的支持-至少对于那些忽视可计算性和复杂性之间区别的人来说-由Church-Turing thesis3。因此，资源实际上总是被视为图灵机（或算法，随机存取机或类似机器）的属性-通常是运行时。4由于数字计算机的流行，由于图灵机与其他计算模型的假设等价性，复杂性理论对算法的这种限制很少被明确考虑，更不用说被视为关注的原因了事实上，这个领域是非常成功的，不仅在理论上，而且在实践中，提供了很好的指导，例如，在计算资源的分配方面1.2非标准计算模型然而，长期以来一直有一个活跃的社区致力于非图灵形式的计算机5：• 求解微分/积分方程的机械装置（例如，[001 pdf 1st-31 files]差异分析器;参见[11• 在平行板之间形成肥皂泡，用于寻找连接给定顶点的最小长度生成网络（可能有额外的顶点）（见[17]）;• DNA计算技术，可以解决有向哈密顿路径问题（见[2]），以及其他图论/组合问题;[3] Church-Turing命题在[12]中介绍，并在[8]和[20]中进行了讨论。[4]话虽如此，我们承认已经考虑到了非标准计算模型的复杂性，尽管在很大程度上是特别的，因此，远非统一的方式。然而，我们注意到，这种计算的真正复杂性并不总是被这种考虑所捕获;值得注意的是，这是真的。在（电路模型）量子计算机的情况下-见节。3.1.[5]我们还注意到，[1]和[14]）的重要性E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）19• 标准（电路模型[18]）和非标准（绝热[15，16]，基于测量[19]，连续变量[9]等）量子计算机;• 用光学方法解决旅行推销员问题（见[13]）等;• 2008年量子物理和逻辑/计算模型的发展的参与者的工作;• 等尽管数字计算机占主导地位，但非图灵系统的重要性越来越大。正如我们可以分析算法（和图灵机等）的复杂性一样，所以我们希望能够分析非标准计算机的复杂性，这样我们就可以比较非标准解决方案与数字解决方案的效率。因此，人们可能希望，非-图灵计算机可以使用传统复杂性理论的现有工具进行充分分析。我们将看到，情况并非如此：以图灵机为中心的度量无法捕捉某些系统的真正复杂性2为什么. . .. . . 非图灵计算机是否需要不同的复杂性分析方法我们在上面声称，传统的基于图灵的复杂性理论忽略了一些计算系统的真正复杂性。在本节中，我们通过展示这样一个系统并讨论其复杂性来证明这一说法。2.1安森美因式分解系统现在我们概述一个分解自然数的模拟系统。这里给出的描述很简短;完整的细节见[4]。(The感兴趣的读者还应该看到[7]，未决的美国专利，该系统是主题，由IBM申请，作者是唯一的发明者，[6]，它描述了系统的修改和在某种意义上的改进版本。最后，该系统被用作[3]中的激励示例正如传统算法一样，系统可以分解的数字大小存在实际限制;然而，与传统算法相比，当输入数字接近该限制时，系统不增加计算时间。对于目前的目的至关重要的是，该限制不是由（运行时、存储器空间等的）考虑所强加的在传统的复杂性理论中，而是由系统用户对精度的要求越来越高6[6]我们在这里看到了需要扩展复杂性理论的第一个线索。20E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）XXnn.ΣXYXYnna，模型（a，b），对感兴趣的区域0≤x≤y≤n进行建模（该图以n= 5为例）。几何公式。首先请注意，自然数n的因式分解任务具有几何公式：该任务正好是在整数网格Z2和曲线y=n（该点的坐标是所寻求的因子中的两因为n的因子是{0，...，n}（实际上，在{1，...，n}），我们只需要在区域0 ≤ x，y ≤ n中搜索网格/曲线点（x，y）;由于（x，y）与（y，x）揭示了相同的因子，我们只需要在区域0 ≤x≤y≤n中搜索。曲线y=是圆锥曲线（特别是双曲线），（x，y）平面和圆锥的交点也是圆锥曲线;因式分解方法网格的实现我们实现整数网格的感兴趣的部分（即，在于上面确定的区域）使用横波源S（波长为2），由反射镜M1、M2和M3反射，以产生一定的干涉图案;该图案中的最大波活动点模型整数网格点，具有最大活动点a，b，0建模网格点（a，b）（其中a，b∈Z）。7年以来来自S的辐射的波长取决于n，它的设置形成了计算见图1的设备中使用的实施整数网格（其中B是一个黑体，吸收一些辐射从S），图。图2表示样本光线8的传播路径，图3表示合成光线i的最大值（如点所示）。在区域R：={（x，y，0）|0 ≤ x ≤ y ≤ 1}，因为cone的实现圆锥由辐射源Pn（圆锥的顶点）和部分圆形传感器Cn（圆是圆锥的横截面）实现。[9]见图4。下标反映了Pn和Cn的位置依赖于n的事实;这些分量的定位形成了计算的输入过程的一部分解释输出。在描述了该装置并提到了输入方法（即，将S的波长以及Pn和Cn的位置设置为适当的n-依赖值）之后，我们转向输出的解释。 来自Pn的辐射在Cn上的一点上显示高振幅干涉（由于波的模式[7]事实上，这些最大活动点模拟了具有相同奇偶坐标的整数网格点。如果我们假设n是奇数，这是足够的，因为n的任何因子都是奇数。（如果需要对偶数进行因式分解，那么在图灵机领域中，迭代地除以2直到得到奇数是计算上微不足道的，可以按照这里所描述的那样进行因式分解。[8]请注意，光线沿自身被M3反射回来;这就产生了驻波。9在[4]中证明，Cn的曲线是从Pn投影曲线所Gn：=.（x，y，0）∈R|1=n→ n到平面y=2−x。 因此，辐射来自于一个点上的PnCn在点（x，y，0）处通过平面z= 0，使得1=n。nnE. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）21Fig. 1. 实现整数网格的设备的布局。图二. 光线从S通过三个反射镜Mi传播回到S的路径。图三. 最大振幅点在区域R中，其中n= 5。22E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）Xy（x，y）-平面。 E x.复杂地，从Pn辐射到point（a，2-a，c）onCnn（2−a）nan（2−a）na一2−a见图4。 实现圆锥的设备的布局。从S）当且仅当它与（x，y）平面相交的点（x，y，0）模拟一个整数点;也就是说，当且仅当1，1∈Z。此外，通过构造Pn和Cn，X y11x·y=n（见脚注9）。因此，这种辐射显示出高振幅的干涉当且仅当1和1是n的因子。 因此，为了解释结果，我们测量Cn上一个点（显示高振幅干涉的点）的坐标将它们转换为一个点（光线穿过的点），穿过.a 、.2−a，0因此，如果从Pn到达的辐射在C n上的（a，2 − a，c）显示高振幅干涉，则。.a、. 2−a，0对所考虑的双曲线上的整数点建模：.n（2-a）和。na是n的因子;相反，所有因子在Cn上都有这样一个点。在建立了如这里所描述的设备，那么，n的因子是这样找到的。我们已经概述了一个模拟因式分解系统。10与现有的算法解决方案相比，它大大改进了运行时，主要是因为它直接物理实现了问题，而不是将问题转换为标准计算模型的人为实例。然而，多项式时间和空间复杂性[11]不是用来强调系统的能力，而是用来强调传统复杂性理论的不完整性。随着n的增加，系统确实需要呈指数级增加的资源（尽管不是特定的时间或空间）;特别是，必须输入n的精度（通过设置S的波长以及Pn和Cn的位置）及其因子读取（通过测量[10]我们重申，[4]是对系统更完整的描述，也是对系统正确运行的证明[11]这些将在下一节中进一步讨论，并在[3]中正式化E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）23nn用作Pn的z坐标和Cn的圆心的z坐标）;nn（v）c.在（iv）inofactors：（a，2−a，c）期间测量的位置的变化→一2−a只有表面上的精确度。如果n∈Z，则n可被检索，且一2−aCn上的点）随n呈指数增长。这表明，对于某些计算机，传统的2.2系统复杂度利用这个系统。使用该系统对n进行因式分解包括：(i) 计算值2（用作S的波长）和.2（将(ii) 通过根据在（i）期间找到的值调整S的波长以及Pn和Cn的高度（z坐标），向系统提供n(iii) 系统中辐射的干扰，这需要辐射在固定距离上的传播（因为相同的装置除了在（ii）中进行的调整之外用于所有n值）;(iv) 测量传感器Cn上高振幅干扰点的位置;以及.n（2−a），.na.我们现在考虑使用因式分解系统的这些步骤的计算复杂度，关于几个资源（在[3]中正式定义时间复杂度。考虑第一时间;我们声称，系统的时间复杂度在大小上是多项式（即，位数）的输入值。请注意，在图灵机领域，上面的步骤（i）和（v）只需要多-nomially长（在n的大小），前者自2和。2需要计算后者因为寻求值n（2-a）和。NA是整数。进一步注意，（ii）- 值得注意的是，执行实际因式分解的步骤（iii）花费恒定的时间;将其与已知的算法方法进行比较，其中计算时间随着n的大小呈指数增加（参见，例如，[10]）。因此，系统的时间复杂度作为一个整体，如所要求的，在输入的大小多项式24E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）nΣΣ、、、n′nn波长2（对于任意x∈R），要因式分解的值取为x+1。因此，假设所提供的波长n′∈n−1，n+1落在区间空间复杂性。类似地，当考虑空间资源时，我们看到只有步骤（i）和（v）的图灵机计算（主要是准备输入和解释输出）消耗的体积随着n的增加而增加，而这些只是多项式增加的体积（在输入的大小上）;对于步骤（ii）-（iv），相同的，固定大小的设备占用相同的固定空间用于所有n值（尽管Pn和Cn的位置取决于n，存在一个有限的，n独立的，有界立方体，该设备位于所有n中因此，系统的空间复杂度是输入大小的多项式在考虑实例（图灵机、随机存取机等）时，时间和空间资源可以说是至关重要的标准的算法计算模型。然而，可以理解的是，仅考虑这些实例而发展的复杂性概念在捕获广泛不同模型的实例的复杂性方面很差;上面的因子分解系统确实具有多项式时间和空间复杂性，但确实需要指数级的随着n的增加而增加资源。 值得注意的是，较大的n值需要指数地输入参数（S的波长以及Pn和Cn的位置）的日益精确的操纵和输出参数（Cn上的点的坐标）的指数级地日益精确的测量，并且我们没有理由不将所需的精度视为一种资源。因此，我们现在考虑系统的精度复杂度，它肯定不是多项式，因此比时间资源更好地捕获系统和空间.精确的复杂性。精度复杂度的目的是捕捉针对模拟/光学/化学）计算机。我们考虑在我们的分解系统中设置波长的例子;其他输入参数（Pn和Cn的位置）和输出参数（Cn上的点的位置），为了简洁起见，我们省略了它们，13可以类似地分析。（精确复杂度的正式描述/定义在[3]中给出给定n，我们希望因式分解，我们打算将波长设置为2。实际上，由于我们对波长控制的技术限制，(we考虑到可变电阻器或类似物的不精确使用），我们可以将波长设置为2，对于某些实际误差，我们仅知道其位于2−λ，2+λ术语“”然而，我们可以设计系统（使用标准模拟技术）从而将非整数输入值舍入到整数以便校正x2×2×212空间，如传统上遇到的整形机等，可以看作是存储容量计算所需的存储器;我们考虑所需物理量的类似概念。[13]省略，虽然部分是为了简洁，但也反映了对其他参数精度要求的考虑的冗余E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）25n+2n−2n（n+2）.21，21“校正”到n的值的1/2-即，如果<11 - ，然后系统处理正确的输入值。注意，这个对λ的约束意味着我们在设置波长时所需的精度随着n的平方增加，因此随着n的大小呈指数增加。然后，我们看到，我们在这里非正式地引入并在[ 3 ]中正式处理的系统传统复杂性理论忽视了显著复杂性测度。3怎么做. ....我们应该测量非图灵计算机的复杂性吗？如何将这种复杂性与图灵机的复杂性进行有意义的比较？我们建议从两个方面来分析非标准计算的复杂性。• 首先，我们主张考虑更多样化的资源选择;例如，我们在上面看到，不仅应该考虑传统的算法度量（如时间和空间），还应该考虑更多的物理度量（如精度）。见第3.1.• 第二，我们希望能够以一种有意义的方式，相对于不同的复杂性资源，比较不同计算模型实例的相应复杂性;因此，我们提倡使用支配的概念，它提供了一个标准，告诉我们哪些计算资源是“相关的”;一旦这些资源被识别出来，它们就见第3.2.3.1非图灵计算我们在上文中注意到：• 传统的复杂性理论和资源（时间、空间等）其中考虑的是图灵机模型的计算，几乎完全排除其他模型的启发• 虽然在考虑图灵机时这显然是足够的，但某些非标准计算机（量子计算机是一个及时的例子）并不适合这些资源;• 有可能（甚至是自然的，一旦问题得到承认）定义资源（例如，精确度），更好地捕捉非图灵计算机的真正复杂性。那么，解决方案是显而易见的：当使用非标准计算模型时，我们应该考虑在计算过程中消耗了哪些资源（包括算法资源和非算法资源），并且应该显式地测量我们的计算相对于这些资源的复杂性;这给出了一个更26E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）完整的画面，以及我们对计算复杂性的理解更有信心。考虑不同资源的必要性在量子计算机的情况下尤其明显。 一个任意的算法（或图灵机或类似的），通过定义完整，可以表示为输入到输出的转换通过从被认为是是“原子”操作。对于一个给定的输入值，在转换过程中执行的这些操作的数量是运行时间的准确度量（或者，根据观点，定义）。类似地，任意量子计算可以表示为准备几个量子比特，然后对这些量子比特的子集应用一系列从完整集合中提取的“原子”幺正操作，然后测量系统。与经典情况一样，这些原子操作的调用的枚举给出了系统复杂性的度量然而，与经典情况一样，结果本质上是运行时间的度量，我们认为这与量子系统并不特别相关14我们建议，通过引入和考虑新的资源，特别是类似于精确度的资源，我们可以更好地封装量子系统的真正复杂性;这种复杂性的出现，毕竟，因为我们对系统进行精确测量的能力有限3.2比较复杂性虽然直接推理问题的计算复杂性似乎天生困难，但确定特定方法（算法，模拟计算机，图灵机等）的复杂性相对容易（一旦考虑适当的资源）。解决问题的方法因此，在大多数情况下，我们对问题复杂性的唯一理解为了改进这样的界限，期望考虑尽可能大的问题的解决方法的集合然而，在实践中考虑的每一个集合都可能是从单个计算模型（通常是图灵机）中获得的解决方法。这是我们无法有意义地比较不同计算模型实例的复杂性因此，需要一个更一般的框架来研究复杂性;特别是，我们希望能够使用这个框架在一致和可比的基础上考虑不同计算模型实例的复杂性--关于几个资源概念;只有当我们能够有意义地[14]量子计算机相对于经典计算机的优势主要来自于纠缠态的使用和这种使用所允许的有效并行性;缺点是从量子系统中读取信息的方式受到严格限制。 这样一个系统的运行时，是既不反映正在执行的‘difficulty’E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）27例如，比较图灵机和DNA计算机各自的复杂性，我们可以开始考虑更大的、模型异构的求解方法集，从而获得问题复杂性的改进边界。因此，我们引入了资源优势(i)支配地位回想一下，在上面的因子分解系统的复杂性分析中，我们认为系统具有指数依赖性的精度比它具有多项式依赖性的时间或空间更相关。这可以通过注意到T，S ∈O（P）而形式化（和抽象的一般概念），但P既不∈O（T）也不∈ O（S），其中P，T和S分别代表精度，时间和空间复杂度函数;我们说，相对于{P，T，S}，精度是主导的。更一般地，相对于集合{X1，...，Xk}的复杂度函数（相对于相应的资源x1，. . . ，xk），则资源xi是支配的当且仅当对于所有j，Xi∈O（Xj）<$Xj∈O（Xi）.通过考虑给定的解决方法（例如，图灵机/模拟计算机/量子系统），我们专注于方法的相关措施-优势形式化资源的相关性：占主导地位的资源施加渐近最大的成本，在某种程度上此外，我们可以根据它们的相关（即，优势）资源（使用因此，我们有一个框架，在其中可以进行有意义的和一致的比较计算模型异构计算机集;该框架可以容纳各种计算模型的实例，并根据各种资源的成本提供结构(This框架和它所基于的优势概念在[5]中进行了更详细的4结论复杂性理论的发展偏向于图灵机模型。这是很容易解释的，在“标准”使用中没有问题我们希望这里描述的想法（在[3]中进行了更充分的探索）能够在某种程度上展示如何进行这种修改，并且QPL/DCM 2008社区的成员发现这些想法既有用又有趣。引用[1] Adamatzky，A.（编辑），Int.J. 《非传统计算》，旧城出版社（2005年起）[2] 阿德曼湖M.，Molecular Computation of Solutions to Combinatorial Problems，Science266（1994），1021-1024[3] Blakey，E.，计算复杂性的模型独立理论：价格：从耐心到精确（及超越）（2008）28E. Blakey/Electronic Notes in Theoretical Computer Science 270（1）（2011）[4] Blakey，E.，一个对因式分解问题的精确解决方案，牛津大学计算科学研究报告CS-RR-07-04（2007）[5] Blakey，E.，优势：一致性比较计算复杂性，（生产中）[6] Blakey，E.，Factorizing RSA Keys，an Improved Answer Solution，Proceedings of the SecondInternational Workshop on Natural Computing，Nagoya，Japan（to appear）（2007）[7] Blakey，E.，System and Method for Finding Solutions，美国专利申请20070165313（2007）[8] Bovet，D.P. 和p.Crescenzi，[9] 布劳恩斯坦，S。L.和A. K. Pati，“Quantum Information with Continuous Variables”，Springer-Verlag（2003）[10] 布伦特河P.，最近的进展和前景的可重构分解算法，LNCS1858（2000），3-20[11] Bush，V.，微分分析器：求解微分方程的新机器，富兰克林研究所杂志，212（1931），447[12] Church，A.，一个无法解决的问题的初等数论，美国。《数学杂志》，58（1936），345-363页[13] Haist，Tobias和Wolfgang Osten，旅行商问题的光学解决方案，光学快报15号。16（2007），10473[14] 霍尔角A. R. 和R.Milner（编辑），Grand Challenges in Computing，The British Computer Society（2004）[15] Kieu，T.D、Hypercomputation with Quantum Adiabatic Processes，TCS317（2004），93[16] Kieu，T. D、希尔伯特第十问题的量子绝热算法[17] Miehle，W.，Link-Length Minimization in Networks，Operations Research6 No. 2（1958），232[18] Nielsen，M. A.和L. Chuang，[19] 放大图片作者：Robert E. Browne和Hans J. Briegel，基于测量的团簇态量子计算，物理评论A68 No.2（2003）[20] Sipser，M.，