alt Hacker Newsif 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.
Replies
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.
> the extended thesis it depends on is "No physical procedure can decide an NP-complete problem in polynomially many steps."
I think part of the confusion here, is that usually the extended church turing thesis means that any physical computation can be efficiently (in polynomial time) simulated by a deterministic turing machine. (And thus if quantum computers exist and BQP is a superset of P, the proposition is false). I've never seen it defined before as above. But im definitely not a complexity theorists.
But isn't PECTT already challenged by quantum algorithms such as Shor and Grover?
> we still dont know the limits of what quantum computers can do.
Well, we don't know the limits of what classical computers can do too (P!=NP is not proven).
While not directly related to P!=NP, historical claims of quantum superiority were occasionally taken down by finding an efficient classical algorithm.