Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Semiclassical Gravity Efficiently Solves NP-Complete Problems

arxiv.org

Post reply on HN
Print view View original

41–46 of 46 posts

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#41

Post by recursivecaveat »

advisedwang wrote: post #34

It doesn't disprove a theory if it results in the physical universe violating NP!=P. In fact, we already know the universe violates NP!=P via the O(N) sorting algorithm[1]: for each element: cut a spaghetti strand to the a the length of the elemnet add strand to bundle of spaghetti hold spaghetti bundle vertical lower spaghetti bundle to a flat surface. loosen grip so that each spaghetti strand comes to rest on flat…

I feel like there's some hidden complexity there. For any finite flat surface there's a point where not all the spaghetti will fit on it simultaneously. So you have to do O(N) compression steps to find the bundle with the long strand. Locating the strand within the bundle also seems non-trivial if it's big enough. Both are easier to see if you start thinking about scaling to sorting like, square miles of spaghetti at a time.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#42

Post by IAmBroom »

anonymousiam wrote: post #31
qarl wrote: post #28

Earlier quoted context omitted.

To be fair - I'd be more shocked by the result that a physical process can solve NP complete problems. If that were true, I'd have expected Mother Nature to have exploited it a long time ago.

It's amazing what some physical processes can do. During the years I worked with laser physicists, I learned that passive optical systems can do crazy things, such as Fourier transforms.

This is done by prisms breaking sunlight into a rainbow, or Newton's Rings of color appearing on oil slicks. Peacocks and bluejays and blue morphos all get their color from notch filters applied to the Fourier transform.

It's a pretty common effect, and frankly trivial. Lensless holographic focusing lenses on sea star exoskeletons are a bit less surprising... but only because they actually evolved, not because it could happen.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#43

Post by IAmBroom »

kadoban wrote: post #40
advisedwang wrote: post #34

It doesn't disprove a theory if it results in the physical universe violating NP!=P. In fact, we already know the universe violates NP!=P via the O(N) sorting algorithm[1]: for each element: cut a spaghetti strand to the a the length of the elemnet add strand to bundle of spaghetti hold spaghetti bundle vertical lower spaghetti bundle to a flat surface. loosen grip so that each spaghetti strand comes to rest on flat…

What does sorting have to do with violating p != np? The common bound on sorting is you can't do better than O(n lg n) worst-case, but that is strictly only for comparison sorts anyway.

For purely randomly distributed groups of n things.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#44

Post by westurner »

westurner wrote: post #39

But does it solve fluids or n-body gravity?

What of the/a dilatant fluid model of gravity which predicts the perihelion of Mercury does not jive with observation?

Doesn't that indicate that CFD is the viable way forward?

The point of the OP is that it's neat or maybe useful that semiclassical gravity solves NP-complete problems; but if the semiclassical model of gravity is insufficient to describe even gravity, why should it be sufficient to solve NPC problems, and what does a sufficient model of n-body fluidic gravity enable low-error predictions of?

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#45

Post by Timwi »

bawolff wrote: post #29
steve_gh wrote: post #21

Earlier quoted context omitted.

But remember that "efficient" in terms of P and NP is about scaling. P == NP doesn't necessarily mean that a practically efficient algorithm can be found. The polynomial exponents involved may be large: O(N^1000) does eventually scale better than O(e^N), but that doesn't mean it is practically useful!

This is pretty unrelated to the topic at hand, but people say that as if its a cop out answer to the conundrum, however i think it would be both the most intersting and most unlikely outcome to the whole p vs np saga. Possibly even more crazy than the answer being uncomputable. Think about what that would mean. It essentially amounts to a loop nested 1000 times would be enough. 1001 tumes is more than needed, 999 tim…

What non-contrived polynomial time problem can you think of that is n^20? I'm really curious.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#46

Post by westurner »

westurner wrote: post #44
westurner wrote: post #39

But does it solve fluids or n-body gravity?

What of the/a dilatant fluid model of gravity which predicts the perihelion of Mercury does not jive with observation? Doesn't that indicate that CFD is the viable way forward? The point of the OP is that it's neat or maybe useful that semiclassical gravity solves NP-complete problems; but if the semiclassical model of gravity is insufficient to describe even gravity, why should it be sufficient to solve NPC problems…

dilatant quantum fluid model of gravity
Post reply on HN