7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ You might also be interested in the brief, sad, history of the mistaken belief that DNA computing was going to be able to solve NP-complete problems in polynomial time. It would actually work quite well if the universe didn't insist that molecules have to take up non-zero amount of space. See cstheory.stackexchange.com/a/2709. $\endgroup$
    – Wandering Logic
    Commented Jun 7, 2015 at 20:16
  • $\begingroup$ I think I finally understood your question. But you confused everyone with your half-baked pipe example with gravity. Basically your question is whether complexity limitations of computational problems can be overcome by using a simulation with an analogical system. The point is that analogical systems are unprecise and give only approximate answers. Also, in some sense analogical system take time to transmit or balance forces. The time unit may be very small, but it exists and complexity of interactions will apply (limited only by lack of precision). $\endgroup$
    – babou
    Commented Jun 9, 2015 at 8:38
  • $\begingroup$ @Juho Is it wise to close? Given the number of answers that make sense, it may not be that bad a question. Only the example did not mean much. I think it says something about the limitations of analog computation, not simply in terms of precision. I would think that, if Church-Turing thesis holds, it gives a relation between the attainable precision and the complexity of problems that may be simulated by the physical phenomenon. Well, something of the kind. It is the first time I am seeing a possible limitation on physics from computation theory. $\endgroup$
    – babou
    Commented Jun 9, 2015 at 9:28
  • $\begingroup$ @Juho Seems fine. I wonder why physicists are refusing to consider possible connection between computation theory and constraints/limitations on physical phenomena. My careful question on this was deleted for being a matter of opinion.(so is string theory, in the eyes of many physicists). $\endgroup$
    – babou
    Commented Jun 9, 2015 at 12:21

3 Answers 3

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The computing power of soap bubbles is greatly overestimated. If you lokk at a very large soap buble, not connected to anything, it can be very far from spherical. $\endgroup$
    – babou
    Commented Jun 8, 2015 at 9:29
7
$\begingroup$

No.

Unless $P=NP$, it's unlikely that any mechanical process can solve an $NP$-hard problem efficiently. Given a mechanical approach to solving a problem, we could run a physics simulation on a computer to get the same result.

Of course this depends on being able to simulate what happens in the real world efficiently. In order for "mechanical polynomial time" to be stronger than "polynomial time" you'd need to find some physical process that can not be simulated efficiently. One possible candidate would be quantum mechanics but that doesn't seem to be what you're asking about (and it is speculated that even quantum computing doesn't allow one to solve $NP$-hard problems efficiently).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ "we could run a physics simulation on a computer to get the same result" -- how so? For all we know, we can not accurately simulate real physics (as opposed to some clunky model of it) on computers. $\endgroup$
    – Raphael
    Commented Jun 8, 2015 at 7:02
  • $\begingroup$ @Raphael The second part of my answer partially addresses this. In order to identify a $NP$-hard problem that can be solved efficiently using a mechanical process, we would need to identify some physical process we can't simulate efficiently with sufficient accuracy. Given that computational problems are discrete (i.e. languages) a discrete approximation of the physical process should often suffice. Even if there existed such a process that could not be simulated, it would certainly be non-obvious (since nobody has managed to name one so far) so the answer to the question is "no" regardless. $\endgroup$
    – Tom van der Zanden
    Commented Jun 8, 2015 at 9:30
  • $\begingroup$ For all we know, the process of an apple falling down a tree is impossible to simulate. All we have is a model (gravitation laws, general relativty, ...) with finite precision, which we can only approximate up to finite precision. That's three uncertainties already. $\endgroup$
    – Raphael
    Commented Jun 8, 2015 at 10:08
  • $\begingroup$ How so that unless P=NP? What if someone creates an entirely new machine. That's non-classical and proves they are not equal to classical machines? Now, we have a new machine that's proven to solve np-complete problems in polynomial time, but is revolutionary and so much different than classical machines. $\endgroup$
    – The T
    Commented Apr 19, 2020 at 19:34
1
$\begingroup$

I'd say "perhaps", but it depends on what you mean by "polynomial mechanical solution". For example, it is possible to sort in constant time in one sense: Given a collection of pieces of spaghetti of various lengths, one could sort them by length by picking up all of them, holding them vertically, and bringing them down on a flat surface. Having done that, the pieces will be sorted.

Now there are lots of perfectly reasonable objections to this algorithm, but in one sense, it does accomplish sorting in constant time, which we know is not possible, if for no other reason than that in the usual computational model it would take $n$ steps just to inspect $n$ strands to know their lengths.

Frankly, I don't know how one might apply this sort of construction to an NP-hard problem, but at the same time I'm not sure that it would be impossible. My feeling is that if one could come up with a solution like this, it would likely be regarded (as the spaghetti sort example) as nothing but a mildly amusing construction.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I don't understand spaghetti sort, assuming you want to sort the noodles by length. When during putting them down do they rearrange? (If you were making a pun, I apologize; it's hard to realize sometimes in this format.) $\endgroup$
    – Raphael
    Commented Jun 8, 2015 at 7:03
  • $\begingroup$ @Raphael It's not constant-time, either. Consider my very accurate spaghetti machine that makes noodles that are 30cm +/-1um long but which has just malfunctioned and thrown a million pieces on the floor. I bet I could process two of those faster than Rick could process the whole batch. $\endgroup$
    – David Richerby
    Commented Jun 8, 2015 at 8:50
  • 1
    $\begingroup$ Spaghetti sorting is not very effective asymptotically. The time is proportional to the longest spaghetti. The speed of light is finite, and it takes that long for a push at the bottom of the spaghetti to propagate to the top. - CC @Raphael $\endgroup$
    – babou
    Commented Jun 9, 2015 at 9:19
  • 1
    $\begingroup$ Aspects of Spaghetti sort were discussed on TCS.SE here. $\endgroup$
    – Juho
    Commented Jun 9, 2015 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.