Problem Detail: Is there any NP-hard problem that we can find a mechanical “polynomial time” solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we can move water. If this pipe system was suitably built, could we solve say some routing problem by seeing if water flows from one node to another? So by a mechanical solution, I mean a physical configuration and not a computer program, i.e. I am not looking for a computer algorithm. I also used “polynomial mechanical solution” to describe a solution on a physical device that runs in time polynomial in the order of the input. For example, a piping system could yield the answer in “number of nodes squared” seconds.
Asked By : user34391
Answered By : Kyle Jones
Scott Aaronson examines “mechanical” solutions to NP-complete problems in the odd and entertaining paper “NP-complete Problems and Physical Reality”. The paper is mostly theoretical discussions of increasingly exotic physical systems but Aaronson does indulge in a bit of empiricism; he tries to use soap bubbles to find Steiner trees. The results were negative:
In general, the results were highly nondeterministic; I could obtain entirely different trees by dunking the same configuration more than once. Sometimes I even obtained a tree that did not connect all the pegs.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43363 Ask a Question Download Related Notes/Documents
