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

31–40 of 46 posts

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#31

Post by anonymousiam »

qarl wrote: post #28
tancop wrote: post #4

Earlier quoted context omitted.

if the PECTT (Physical Extended Church-Turing Thesis) is true then the current standard way of connecting classical gravity with quantum mechanics is wrong. the authors take it as evidence for full quantum gravity because the alternative is changing the Einstein equations in some arbitrary complex way. im not a physicist so this might be a bad explanation. the extended thesis it depends on is "No physical procedure c…

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.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#32

Post by einpoklum »

bawolff wrote: post #13
einpoklum wrote: post #11

From the abstract: "Assuming [assumptions] we show that ... can in principle solve..." Yeah, well, you know... that doesn't sound as promising as the title.

Assuming X is true, that implies Y. We don't think Y is true therefore we now doubt that X is true, is a very standard thing to do in math.

Yes, but the title suggests that "[method] solves NP-complete problems", and sounds kind of like "Quantum-Physics-related trick solves NP-complete problems".

Moreover - it doesn't even solve NPC problems conditionally, but that show that "in principle" they should be / would be solvable.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#33

Post by Maxatar »

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.

Hmm... I suppose it can come across as pedantic, but physical processes as a whole can do anything that can be done, hence it shouldn't come as a surprise that there exists a physical process that can perform a Fourier transform, or any computable process whatsoever.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#34

Post by advisedwang »

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 surface

   while there is spaghetti in the bundle:
     lower a second flat surface above the bundle until it touches the topmost spaghetti piece
     remove the piece, and output it's length
[1] which I learned about in "The New Turing Ominbus" by A K Dewdney

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#35

Post by SyzygyRhythm »

anonymousiam wrote: post #30
SyzygyRhythm wrote: post #12

I was skimming the paper and came to this: > This transformation is like an AND gate - it ignores the index qubit and places the flag qubit in the state |1> if and only if either of the original components had the state |1> for the flag qubit. Shouldn't that be an OR gate? Not only does the description above say "if and only if either of the original components had the state |1>", which is an OR, but the truth table…

Demorgan's theorem says AND and OR are equivalent, and only depend upon the polarity of the bits. So if "state |1>" is a binary zero, AND is the proper logical operator.

Yes, I think that was implied in my original post, that if you define |0> as logical 1 then it works as an AND. It just seems confusing and unnecessary when they could have framed it to be consistent with classical logic.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#36

Post by DroneBetter »

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 hate every time i hear about spaghettisort.

it is still O(n) weight to transport, so O(n^2) amortised; if you liken having a stronger hand that can carry more spaghetti to parallelisation, it's beaten by O(log^2 n) sorting algorithms on parallelised classical computers.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#37

Post by SyzygyRhythm »

slwvx wrote: post #26
SyzygyRhythm wrote: post #12

I was skimming the paper and came to this: > This transformation is like an AND gate - it ignores the index qubit and places the flag qubit in the state |1> if and only if either of the original components had the state |1> for the flag qubit. Shouldn't that be an OR gate? Not only does the description above say "if and only if either of the original components had the state |1>", which is an OR, but the truth table…

Are you sure you're looking at the right paper? I don't find the sentence you mention in the paper.

Doh! You are correct. I had been looking at a previous paper (which this new paper references). The previous paper showed that you can use any non-linearity in QM to solve NP-complete problems, and the new one shows that semi-classical gravity + QM has such a non-linearity. The earlier paper: https://arxiv.org/pdf/quant-ph/9801041

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#38

Post by cout »

Maxatar wrote: post #33
anonymousiam wrote: post #31

Earlier quoted context omitted.

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.

Hmm... I suppose it can come across as pedantic, but physical processes as a whole can do anything that can be done, hence it shouldn't come as a surprise that there exists a physical process that can perform a Fourier transform, or any computable process whatsoever.

I agree. To me it's more interesting that there exists a physical process that performs a Fourier transform than that there could exist such a process. If it can be done on pen and paper, it's already proven that it can be done in a physical system, since the pen and paper are physical.

Re: Semiclassical Gravity Efficiently Solves NP-Complete Problems

#40

Post by kadoban »

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.

Post reply on HN