Macroscopic quantum objects cannot exist if P ≠ NP? • Hacker News Board

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#71

Post by sk8ingdom » Fri, Jul 25, 2014, 5:18 PM UTC

swombat wrote: post #13

raverbashing wrote: post #6

I'm not buying it 1 - P=NP is a mathematical problem. It has nothing to do with Physics. Physics has to do with Mathematics but one should be very careful when extrapolating (range, constraints, etc). 2 - Nature has no problem whatsoever solving complicated equations. Our mathematical models are the ones who suffer to model simple everyday stuff in Physics. Turbulence and Navier-Stokes equations, electromagnetic prop…

Unless, of course, our entire reality is running on a very powerful, but not infinitely powerful computer, and the Great Programmers in the Sky decided to cheat by putting in a hack that cuts off quantum behaviour at a larger scale... Unlikely, but cute...

Relevant xkcd: http://xkcd.com/224/

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#72

Post by TheLoneWolfling » Fri, Jul 25, 2014, 5:56 PM UTC

PeterisP wrote: post #44

Strilanc wrote: post #24

I hope Scott Aaronson blogs about this article, because it espouses several of the wrong-facts he complains about and then cites him . - Limitations on computers within physics are not limitations on physics itself . Analogously, you can simulate system so simple that a computer can't be made in them without your computer unmaking itself. Relevant: xkcd.com/505 - We do understand why we don't observe superpositions.…

An interesting point is that limitations on math (i.e., things that would be true regardless of the details of the physical world) would put limitations on any physics simulations - including hypothetical physics simulations done by someone outside of our universe with potentially different physical limitations. So the point of the article is something like - if phenomenon-X can't be simulated by anyone, no matter ho…

The problem is that there is no proof that there is any such thing as something that would be true regardless of the details of the physical world.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#73

Post by TheLoneWolfling » Fri, Jul 25, 2014, 5:57 PM UTC

An interesting tidbit:

If the smallest proof for something takes up more than ~10^123 bits, or the fastest proof requires more than ~10^120 operations, it cannot be proven in our universe.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#74

Post by baddox » Fri, Jul 25, 2014, 6:57 PM UTC

dllthomas wrote: post #70

baddox wrote: post #57

Earlier quoted context omitted.

Technically P=NP is just about Turing machines (and thus all Turing complete systems, which includes all the computers humans have produced). As far as I know there is no evidence of real super-Turing systems, but the concept has been theorized. http://en.wikipedia.org/wiki/Hypercomputation

Right. "There exists a device that can solve NP problems in P time" is a different statement than "P=NP". Regarding "Hypercomputation" in particular, I've typically encountered it in the context of "solving problems a TM can't solve" rather than "solving problems a TM can solve but asymptotically faster" - is it actually used for both? A skim of the article didn't clarify.

That's a good point. The first sentence of the Wikipedia article says "Hypercomputation or super-Turing computation refers to models of computation that go beyond, or are incomparable to, Turing computability." The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to. :)

Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster.

Re: Macroscopic quantum objects cannot exist if P ≠ NP?

#75

Post by dllthomas » Fri, Jul 25, 2014, 7:11 PM UTC

baddox wrote: post #74

dllthomas wrote: post #70

Earlier quoted context omitted.

Right. "There exists a device that can solve NP problems in P time" is a different statement than "P=NP". Regarding "Hypercomputation" in particular, I've typically encountered it in the context of "solving problems a TM can't solve" rather than "solving problems a TM can solve but asymptotically faster" - is it actually used for both? A skim of the article didn't clarify.

That's a good point. The first sentence of the Wikipedia article says "Hypercomputation or super-Turing computation refers to models of computation that go beyond, or are incomparable to, Turing computability." The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to. :) Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve…

'The "incomparable to" part is sufficiently vague to shoehorn in asymptotic improvements if we want to.'

I totally agree, which is part of why the article didn't clear it up.

"Of course, an Zeno machine, or a machine that can solve the halting problem, could also certainly solve problems a TM can solve but asymptotically faster."

A Zeno machine, for sure. It is not immediately clear to me that this necessarily holds for anything that can solve the halting problem - what about a TM plus a halting problem oracle that would tell you in 2^(size of TM) whether a TM halts?

Of course the real question is whether asymptotically faster is enough to be "hypercomputation". Necessity is also interesting, but not the same thing.