Semiclassical Gravity Efficiently Solves NP-Complete Problems

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 can decide an NP-complete problem in polynomially many steps." imo thats a very strong and controversial assumption when we still dont know the limits of what quantum computers can do.

Semiclassical gravity is the best we can currently do for a theory of gravity without invoking speculative ideas that are currently untestable. If the paper holds up (I haven't read it), then there are several possibilities:

1. Maybe P = NP, and semiclassical gravity isn't special. 2. Maybe P = NP, and the way we'll prove it is finding an efficient way to simulate semiclassical gravity. 3. P = NP is a hypothesis about traditional theories of computation, but they don't rule out that we can build a special machine that solves them. There's a stronger hypothesis, the extended Church-Turing thesis (ECTT), that says this is impossible. Maybe the extended Church-Turing thesis is wrong, and this is how we'll show it. 4. If ECTT thesis is right, then maybe we can conduct an experiment where semiclassical gravity fails. This gives us a clue to new physics. 5. If we can't eventually conduct an experiment, then at least we learn about a new angle on complexity -- problems that can be efficiently solved this way but not by a deterministic Turing machine.

Both quantum mechanics and general relativity are thought to satisfy the ECTT, so the fact that our most experimentally successful combination of the two doesn't is of some interest. (Semiclassical gravity is thought to fail eventually, but in a way that's out of reach of current experiments.)

They use what looks like an impossible computational result to back into the idea that this is indirect evidence that gravity is quantized.

The controversy here is whether gravity is continuous (as classical Einstein models it) all the way down, or if the large scale behavior is built on a quantum foundation like everything else.

As far as I know most physicists believe gravity must be quantized, but we have no theory for it that works and plays nice with the well validated relativistic stuff at scale.

We have some candidates like string theory and loop quantum gravity but testing and refining them requires accelerators the size of the solar system or direct access to a black hole. The latter was the plot of Interstellar.

They essentially are saying semiclassical gravity (a broader theory subsuming classical) is theoretically incorrect. Like doing the konami code IRL and getting infinite money.

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

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.

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?

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.

That's the whole point of the article:

"We show [Assuming {competing physics theory} then {P = NP}]"

(or something along the lines)

"But we actually think P != NP... so [Assuming {P != NP} then {competing physics theory} cant be true]"

Shocking..

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.

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.

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.