{"id":"arxiv/2610.09855","url":"https://arxiv.org/abs/2610.09855","tags":["hep-th","gr-qc","math-ph","math.MG","quant-ph"],"score":0,"title":"Spacetime Quasicrystals and Computational Complexity Theory in the Road Towards Quantum Gravity","domain":"hep-th","source":"arxiv","authors":["Sotirios Mygdalas"],"reviews":0,"subject":"hep-th","summary":"Part I: Semiclassical Gravity Efficiently Solves $\\mathsf{NP}$-Complete Problems Assuming the gravitational field is classical and that it couples to quantum fields via the semiclassical Einstein field equations (EFEs), we show that the weak-field dynamics of a massive and non-relativistic qubit can in principle be used to solve an $\\mathsf{NP}$-complete problem in polynomial time. We attribute this vast computational power to the non-linear qubit dynamics afforded by the semiclassical EFEs. Consequently, the above two assumptions entail a violation of the Physical Extended Church--Turing…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}