4
$\begingroup$

Consider the problem of finding the convex hull for $n$ points on a plane. No constant time algorithms exist to solve it.

Now say you represent the points as poles of equal height that you hammer into the ground. You then place a giant stretched rubber band around them and let go of it. The elasticity of the rubber band will cause it to take the shape with the least possible perimeter (it will "tightly embrace" the poles). The shape it takes on is the convex hull of the poles. The amount of time it takes for the rubber band to trace the shape of the convex hull is independent of the number of poles.

Then, for this case, it would appear the laws of physics are "causing" the problem to be solved faster ($O(1))$ than any known algorithm.

Say it is shown that the minimum time for some problem to be solved computationally is bounded by $\mathbb{\Omega }(f(n))$ for some problem variable $n$. I'm curious if the bound can be violated as a consequence of the laws of physics acting on something.

$\endgroup$
3
  • 3
    $\begingroup$ You could view the world as a highly parallel computer where "computation" is being performed on all points of the table cloth simultaneously. In this way I think you can say the number of operations needed for the computation is the same but the computer can do almost all of the computations at the same time. Remember that O() notation isn't about time, it's about the size of the problem (number of operations). $\endgroup$ Oct 7, 2014 at 6:01
  • $\begingroup$ There are a couple of problems with your assumption that the world is a computer running algorithms. For one thing, it only runs one algorithm, which we don't even know, yet. You can't stop this program, you can't reset it, you can't even change the parameters and, worst of all, it doesn't let you debug its internal state at all. $\endgroup$
    – CuriousOne
    Oct 7, 2014 at 6:53
  • 1
    $\begingroup$ The physical rubber band and poles can be thought of as an "analog computer" specifically designed to solve the convex hull problem. The idea of building a physical model to solve a problem is an old one: e.g. build a scale model of a bridge to see if it can support weight. $\endgroup$
    – DanielSank
    Oct 7, 2014 at 15:24

2 Answers 2

3
$\begingroup$

The current working assumption of most physicists who are researching computational complexity is that the computation achievable in classical physics is equivalent in power, up to polynomial factors, with a classical Turing machine, and that the computation achievable in quantum physics is equivalent, up to polynomial factors, with a quantum Turing machine.

As an entry into the vast and fascinating literature on this topic, I recommend:

David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer (1985) http://www.daviddeutsch.org.uk/wp-content/deutsch85.pdf

Also, the first chapter of my thesis gives a brief summary and list of references on this topic: https://arxiv.org/abs/0809.2307

Your question is a bit more fine-grained than what I have referenced above, since your question is about constant vs. linear time algorithms. Such a speedup wouldn't contradict standard complexity-theoretic assumptions, since it could be effectively due to conventional classical parallel computing. However, I don't actually think that the computation time for your rubber band computer is asymptotically constant. If you imagine that the rubber band can only be stretched around the posts at some finite speed (the speed of light provides an upper limit) then the more posts you have, the longer it will take you to put the rubber band around them. You could try to compensate by making the posts smaller and closer together but this runs into limitations too- one can't make the posts less than one atom thick! So, in practice, your rubber band computer might achieve approximately linear runtime for reasonable size problem instances. However, a complexity theorist, who is interested in the asymptotic scaling of the runtime in the limit that the size of the problem goes to infinity, would say that the rubber band computer does not achieve constant time.

Incidentally, a similar example, namely a soap-bubble computer for finding minimum spanning trees (which is an NP-hard problem) is analyzed in:

Scott Aaronson, NP-complete problems and physical reality (2005) https://www.scottaaronson.com/papers/npcomplete.pdf

$\endgroup$
2
$\begingroup$

In a sense, yes the bound can be violated, but not because is violated, but because the algorithm is completely different. Let me explain.

In Mathematics, elements and rules are defined according to a strict logic and from them, conclusions are drawn following this methodical and univocal logic. It is a milestone of human thinking.

This allows to "mathematize" nature (although historically nature and practical problems have pushed forward mathematical abstract elements). That is, to establish a correspondence between real entities and phenomena based on their relevant similarities to elements in math. In other words, is to say that waves in a pound from a thrown stone are circles, that orbits are ellipses or that quantum states correspond to a wave function.

Once you can establish the connection you can use all the logical conclusions from mathematics to further study and understand nature in a much complex way than simple observation allows, and formulate natural behaviour in form of laws and mathematical relations.

Also you correspond phenomena with problems mathematically formulated, much like establishing that the amount of charge inside a closed surface is proportional to the integral of E through it, or that the shape of a drop is that which minimizes its surface energy.

Finally, an algorithm would be the structured method for solving a mathematical problem, a set of instructions to find a solution to a question formulated in mathematical terms.

That being said, our algorithms reflect our understanding of nature through the best logic we have come up with. But nature already "solves" these and many other problem through mechanisms still out of our grasp.

Nevertheless, we can and have used nature "computational skills" to our advantage, like differentiatig/integrating complex functions instantaneously, or the use of PNN to solve problems that would be very difficult to even formulate mathematically. Humans compute in complex situations really fast things like how to maintain equilibrium, and the our mathematical algorithms for this are still in baby steps.

So answering your question, our algorithms are in a way the best we can come up with to solve a problem that generally has a counterpart in nature. But natural phenomena do not follow mathematical algorithms and are not constrained by this. The question is then, how does nature "compute"? We don't know yet.

$\endgroup$

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.