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.
Could an NP-hard problem have a mechanical or physical solution method?
complexity theory;np hard;p vs np;physics
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.