Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
| Autor: | Çivril, Ali |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 15 pages, more formal definitions unit reductions, proof (of the almost obvious fact) that unit operations are distinct from unit instance operations |
| Databáze: | arXiv |
| Externí odkaz: |
|