Semiclassical Gravity Efficiently Solves NP-Complete Problems

Researchers propose that semiclassical gravity—where the gravitational field remains classical while coupling to quantum fields—can solve NP-complete problems in polynomial time through non-linear dynamics in the Einstein field equations. This theoretical result would violate the Physical Extended Church-Turing Thesis and suggests that gravity must be quantized to prevent such computational capabilities. The authors argue this provides evidence that gravity should be a quantum theory rather than a classical one.