P/NP, and the quantum field computer
P/NP, and the quantum field computer
复制标题
DOI：
10.1073/pnas.95.1.98
复制
发表时间：
1998-01-06
影响因子：
11.1
通讯作者：
Freedman, MH
中科院分区：
文献类型：
--
作者：
Freedman, MH
计算机科学中的中心问题是猜想两个复杂性类，P（多项式时间）和NP（非确定性多项式时间-大致上是那些可以在多项式时间内检查建议解决方案的决策问题），在标准图灵计算模型中是不同的：P不等于NP。作为一般性的，我们建议，每个物理理论支持计算模型，其功率是有限的物理理论。众所周知，经典物理学支持图灵机的大量实现。非阿贝尔拓扑量子场论表现出必要的数学特征，以支持能够在多项式时间内解决所有P问题的模型，这是一个计算上难以处理的类。具体地说，维滕[维滕，E.（1989）Commun. Math.Phys.121，351-391]已经用琼斯多项式的值确定了某个SU（2）场理论中的期望值[Jones，V.（1985）Bull.Am. Math.Soc.12，103-111]，其是#P-hard [Jaeger，F.，Vertigen，D. & Welsh，D.（1990）Math.Proc.Comb.Philos.Soc.108，35-53]。这表明，一些物理系统的有效拉格朗日包含一个非阿贝尔拓扑项可能被操纵，作为一个模拟计算机能够解决NP甚至#P-困难的问题在多项式时间。定义这样的系统并解决制备和测量中固有的准确性问题是一个尚未解决的主要问题。
The central problem in computer science is the conjecture that two complexity classes, P (polynomial time) and NP (nondeterministic polynomial time-roughly those decision problems for which a proposed solution can be checked in polynomial time), are distinct in the standard Turing model of computation: P not equal NP. As a generality, we propose that each physical theory supports computational models whose power is limited by the physical theory. It is well known that classical physics supports a multitude of implementation of the Turing machine. Non-Abelian topological quantum field theories exhibit the mathematical features necessary to support a model capable of solving all #P problems, a computationally intractable class, in polynomial time. Specifically, Witten [Witten, E. (1989) Commun. Math. Phys. 121, 351-391] has identified expectation values in a certain SU(2)-field theory with values of the Jones polynomial [Jones, V. (1985) Bull. Am. Math. Soc. 12, 103-111] that are #P-hard [Jaeger, F., Vertigen, D. & Welsh, D. (1990) Math. Proc. Comb. Philos. Soc. 108, 35-53]. This suggests that some physical system whose effective Lagrangian contains a non-Abelian topological term might be manipulated to serve as an analog computer capable of solving NP or even #P-hard problems in polynomial time. Defining such a system and addressing the accuracy issues inherent in preparation and measurement is a major unsolved problem.