Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] A Classical World

Expand Messages
  • Lance
    We need to rewrite the traffic laws in this country because they don t handle flying cars. We don t have flying cars, you say. We might have flying cars in the
    Message 1 of 1 , Jan 5, 2006
    • 0 Attachment
      We need to rewrite the traffic laws in this country because they don't handle flying cars. We don't have flying cars, you say. We might have flying cars in the next couple of decades so the current traffic laws no longer apply.

      Keep that argument in mind as you read the following paragraph from David Bacon.

      If today someone was to prove that P does not equal NP for a classical computer, would we be satisfied? Well certainly we would be very excited and this would be the breakthrough of the century in computation, but because the universe is fundamentally quantum mechanical, would we really be satisfied that the intractability of NP-complete problems had been shown? Quantum computers open up an entire bag of worrying about the foundations of computational complexity. It is dangerous to say this, of course: if this view is correct, then the hard work of classical computational theory might have been in vain. But if this is the correct view, then we need to begin weaning ourselves off of the classical model of computation.
      Dangerous indeed. Bacon is not the first one to make such statements, Gilles Brassard made much stronger pronouncements as far back as 1990.

      Did the theory of relativity mean the hard work of classical mechanics was in vain? Of course not. When we drive a car we don't need to worry about relativistic effects, they simply don't amount to much at that level.

      We don't know how quantum mechanics will actually play out in a computer that would require the entanglement and manipulation of tens of thousands of quantum bits. Maybe we can harness the full power of quantum computation, maybe we can't. At this point we simply don't know.

      I support research in quantum complexity, as long as quantum computing remains a possibility we should try and understand its computational power. But not until we all have fast quantum computers on our desks should we even think of abandoning classical complexity. And in our current state of affairs, where creating a quantum computer that factors faster than my daughter is a pipe dream, classical computational complexity serves us very well indeed.

      --
      Posted by Lance to Computational Complexity at 1/05/2006 08:28:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.