Semiclassical Gravity Efficiently Solves NP-Complete Problems
2026/06/11 by Matthew Fox, Chaitanya Karamchedu, Sotirios Mygdalas · 8 voices
#gr-qc #hep-th #quant-ph
paper · pdf
Abstract
Assuming the gravitational field is classical and that it couples to quantum fields via the semiclassical Einstein field equations, we show that the weak-field dynamics of a massive and non-relativistic qubit can in principle be used to solve an NP-complete problem in polynomial time. We attribute this vast computational power to the non-linear dynamics afforded by the semiclassical Einstein field equations. Consequently, the above two assumptions entail a violation of the Physical Extended Church--Turing Thesis, which we regard as evidence for the quantization of gravity.
Citations
Discussions
- Semiclassical Gravity Efficiently Solves NP-Complete Problems [hn, 74 points, 41 comments]
- Semiclassical Gravity Efficiently Solves NP-Complete Problems https://arxiv.org/abs/2606.14806 (https://news.ycombinator.com/item?id=48565326) [bsky, 0 points, 0 comments]
- Semiclassical Gravity Efficiently Solves NP-Complete Problems [bsky, 0 points, 0 comments]
- Semiclassical Gravity Efficiently Solves NP-Complete Problems https://arxiv.org/abs/2606.14806 [bsky, 0 points, 0 comments]
- Semiclassical Gravity Efficiently Solves NP-Complete Problems https://arxiv.org/abs/2606.14806 (https://news.ycombinator.com/item?id=48565326) [bsky, 0 points, 0 comments]
- 📰 Semiclassical gravity efficiently solves NP-complete problems, demonstrating potential for significant advancements in computational complexity theory and practical applications. 🔗 https://arxiv.o [bsky, 0 points, 0 comments]
- Semiclassical Gravity Efficiently Solves NP-Complete Problems https:// arxiv.org/abs/2606.14806 # arxiv [mastodon, 0 points, 0 comments]
- Semiclassical Gravity Efficiently Solves NP-Complete Problems https://arxiv.org/abs/2606.14806 [comments] [40 points] [bsky, 0 points, 0 comments]
Related