×

P/NP, and the quantum field computer. (English) Zbl 0895.68053

Summary: 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\(\neq \)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, E. Witten [Commun. Math. Phys. 121, No. 3, 351-399 (1989; Zbl 0667.57005)] has identified expectation values in a certain \(SU(2)\)-field theory with values of the Jones polynomial [V. Jones, Bull. Am. Math. Soc., New Ser. 12, 103-111 (1985; Zbl 0564.57006)] that are #P-hard [F. Jaeger, D. Vertigen and D. Welsh, Math. Proc. Camb. Philos. Soc. 108, No. 1, 35-53 (1990; Zbl 0747.57006)]. 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.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] LETT MATH PHYS 2 pp 247– (1978) · Zbl 0383.70017
[2] Bennett 54 (5) pp 3824– (1996) · Zbl 1371.81041
[3] MATH PROC CAMBRIDGE PHILOS SOC 108 pp 35– (1990) · Zbl 0747.57006
[4] BULL AM MATH SOC 12 pp 103– (1985) · Zbl 0564.57006
[5] COMMUN MATH PHYS 121 pp 351– (1989) · Zbl 0667.57005
[6] COMMUN MATH PHYS 141 pp 423– (1991) · Zbl 0738.53041
[7] MATH RES LETT 2 pp 239– (1995)
[8] MOD PHYS LETT A 3 pp 325– (1988)
[9] NUCL PHYS B 426 pp 19– (1994) · Zbl 0996.81510
[10] COMMUN MATH PHYS 156 pp 435– (1993) · Zbl 0788.58013
[11] PROCEEDINGS OF THE TH ICALP LECTURE NOTES IN COMPUTER SCIENCE 71 pp 520– (1974)
[12] IBM J RES DEV 17 pp 525– (1973) · Zbl 0267.68024
[13] INT J THEOR PHYS 21 pp 467– (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.