Matematičeskie struktury i modelirovanie

If Many Physicists Are Right and No Physical Theory Is Perfect, Then by Using Physical Observations, We Can Feasibly Solve Almost All Instances of Each NP-Complete Problem

Olga M. Kosheleva, Michael Zakharevich, Владик Крейнович

Published Jan 1, 2014• 4 citations

Abstract

Many real-life problems are, in general, NP-complete, i.e., informally speaking, are difficult to solve -- at least on computers based on the usual physical techniques. A natural question is: can the use of non-standard physics speed up the solution of these problems? This question has been analyzed for several specific physical theories, e.g., for quantum field theory, for cosmological solutions with wormholes and/or casual anomalies, etc. However, many physicists believe that no physical theory is perfect, i.e., that no matter how many observations support a physical theory, inevitably, new observations will come which will require this theory to be updated. In this paper, we show that if such a no-perfect-theory principle is true, then the use of physical data can drastically speed up the solution of NP-complete problems: namely, we can feasibly solve almost all instances of each NP-complete problem.

Related papers

If Many Physicists Are Right and No Physical Theory Is Perfect, Then the Use of Physical Observations Can Enhance Computations

Olga M. Kosheleva, Michael Zakharevich

Many real-life problems are, in general, NP-complete, i.e., informally speaking, are difficult to solve – at least on computers based on the usual physical techniques. A natural question is: can the use of non-standard physics speed up the solution of these problems? This question has been analyzed for several specific physical theories, e.g., for quantum field the-ory, for cosmological solutions with wormholes and/or casual anomalies, etc. However, many physicists believe that no physical theory is perfect, i.e., that no matter how many observations support a physical theory, inevitably, new observations will come which will require this theory to

Journal of Uncertain SystemsJan 1, 20144 citations

NP-complete Problems and Physical Reality

Scott Aaronson

Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.

arXiv:quant-ph/0502072Feb 12, 2005153 citations

Guest Column: NP-complete problems and physical reality

Scott Aaronson

ACM SIGACT NewsMar 1, 2005226 citations

P/NP , and the quantum field computer

Michael Hartley Freedman

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.

Proceedings of the National Academy of SciencesJan 6, 1998222 citations

Quantum computers and intractable (NP-complete) computing problems

V. Černý

In this paper we discuss physical aspects of intractable (NP-complete) computing problems. We show, using a specific model, that a quantum-mechanical computer can in principle solve an NP-complete problem in polynomial time; however, it would use an exponentially large energy for that computation. We conjecture that our model reflects a complementarity principle concerning the time and the energy needed to perform an NP-complete computation.

Physical Review AJul 1, 199338 citations

Principles of Constructing a Correct Microscopic Theory

B. V. Vasiliev

In our time, experimental physicists have obtained data on a very large number of phenomena and objects of the physical world. Very rarely there is a situation when theoretical physicists do not have enough experimental data to understand some known fundamental law of Nature. This situation arose almost a hundred years ago and sparked a discussion between A. Einstein and N. Bohr on the probabilistic nature of microcosm phenomena. From the time, it seemed that most physicists are inclined to believe that the proponents of a quantum explanation of the randomness of the phenomena of radioactive decay are right. Now this problem has been solved experimentally. The results of these measurements [1] show that A. Einstein and other proponents of determinism were right. In most cases, theoretical models are based on some already existing experimental data and are intended to explain them. At the same time, in the twentieth century, among microscopic, well-mathematically based models, there were several that raise doubts about their correctness, since they cannot explain a number of other experimental data that can be attributed to the fundamentally important properties of the studied objects [2] [3]. Therefore, the usual criterion for the correctness of the theory, which consists of its agreement with the measurement data, is ambiguous in this case. An additional criterion for the correctness of a microscopic theory can be formulated if it is assumed that the microscopic theory must be quantum one. The coefficients of quantum equations are world constants. Therefore, the solutions of these equations must be equalities made up of world constants only. For this reason, a correct microscopic model must rely on equalities consisting of world constants only. This criterion is shown to work successfully for models of superfluidity and superconductivity, for models of a number of particles, and models of the star interior.

Journal of Modern PhysicsJan 1, 20202 citations