Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
Ali Çivril · arXiv (Cornell University) · 2021
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.