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, Владик Крейнович · scholarworks - UTEP (The University of Texas at El Paso) · 2014
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.