Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP

Abstract

We lay the foundations of a new theory for algorithms and computational complexity by parameterizing the instances of a computational problem as a moduli scheme. Considering the geometry of the scheme associated to 3-SAT, we separate P and NP. In particular, we show that no deterministic algorithm can solve \textsf{3-SAT} in time less than $1.296839^n$ in the worst case.

arXiv commentThis was an early and insufficiently verified attempt. Errors affecting the main results were later identified, and the manuscript has been withdrawn

Cited by in corpus (1)

• Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$