Mathematical results related to the heuristic Principle of Computational Equivalence

[Kreinovich, Vladik]

True, but there are many problems like Graph Isomorphism which many people believe to be in between: not feasible, but not NP-hard either

From: fom-bounces at cs.nyu.edu <fom-bounces at cs.nyu.edu> On Behalf Of Joe Shipman
Sent: Thursday, May 7, 2020 10:21 AM
To: José Manuel Rodríguez Caballero <josephcmac at gmail.com>
Cc: Foundations of Mathematics <fom at cs.nyu.edu>
Subject: Re: Mathematical results related to the heuristic Principle of Computational Equivalence

There are 2 closely related but distinct parts to this:
1) NP complete problems are everywhere and whether or not there may not be a physically feasible way to solve them, they are polynomially equivalent to each other
2) Turing-complete problems and associated Godel-undecidable propositions are everywhere, any reasonably complex system can do computation and therefore questions about its limit behavior can not be answered and simulations of its dynamics can not be “sped up” (even if P=NP)

The second seems easier to establish if you count resolving the P-NP question as part of the first, but if you don’t, then the first seems easier.

— JS

Sent from my iPhone


On May 7, 2020, at 11:56 AM, José Manuel Rodríguez Caballero <josephcmac at gmail.com<mailto:josephcmac at gmail.com>> wrote:

Dear FOM members,
  The Principle of Computational Equivalence [1, 2], due to S. Wolfram, is the heuristic statement that almost all processes (involving classical computations) that are not obviously simple are of equivalent sophistication. This principle has been recognized as relevant for biology by Prof. Robert Sapolsky [3] and there may be even a quantum version of it if J. E. Andersen's conjecture is proved [4].

  One of the tasks of mathematicians is to find conditions for which a heuristic principle is valid and counterexamples outside this domain. So, I would like to ask for references concerning mathematical results related to this principle, which may be known under a different name. I guess that the main challenge is to find precise conditions for expressing the intuitive notion of not obviously a simple computational process.

Sincerely yours,
Jose M.

References:

[1] Wolfram, S. "The Principle of Computational Equivalence." Ch. 12 in A New Kind of Science. Champaign, IL: Wolfram Media, pp. 5-6 and 715-846, 2002.
URL = https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence/

[2] Wolfram, S., Interview about the Principle of Computational Equivalence.
URL = https://www.inc.com/allison-fass/stephen-wolfram-principle-of-computational-equivalence.html

[3] Robert Sapolsky, Lecture 22. Emergence and Complexity.
URL = https://youtu.be/o_ZuWbX-CyE

[4] J. E. Andersen, Folding of proteins and RNA using the quantum topology of moduli spaces (the conjecture is in the last slide)
URL = https://cityu-ias-www-upload.s3.amazonaws.com/eventpowerpoint/src/07-2%20-%20Prof.%20J%C3%B8rgen%20ANDERSEN_6bc1bc1d-a19d-47c6-ab55-2a01d99b11d3.pdf


-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20200507/7bc050e1/attachment.html>