Here’s Scott Aaronson describing people (university professors at RPI) who claim that the physical universe efficiently solves NP-hard problems.
This doesn’t refute what you are responding to. Saying the universe can’t solve a general NP problem in polynomial time is not the same thing as saying the universe cannot possibly solve specific instances of generally NP-complete problems, which is Tyrrell_McAllister’s point, as far as I can parse. In general, the traveling salesman is NP-complete, however there are lots of cases where heuristics get the job done in polynomial time, even if those heuristics would run-away if they were given the wrong case.
To use Aaronson’s soap bubbles, sometimes the soap bubble finds a Steiner tree, sometimes it doesn’t. When it DOES, it has solved one instance of an NP-complete problem fairly quickly.
This doesn’t refute what you are responding to. Saying the universe can’t solve a general NP problem in polynomial time is not the same thing as saying the universe cannot possibly solve specific instances of generally NP-complete problems, which is Tyrrell_McAllister’s point, as far as I can parse. In general, the traveling salesman is NP-complete, however there are lots of cases where heuristics get the job done in polynomial time, even if those heuristics would run-away if they were given the wrong case.
To use Aaronson’s soap bubbles, sometimes the soap bubble finds a Steiner tree, sometimes it doesn’t. When it DOES, it has solved one instance of an NP-complete problem fairly quickly.