Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910334255628288 |
|---|---|
| author | Çivril, Ali |
| author_facet | Çivril, Ali |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_07386 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP Çivril, Ali Computational Complexity 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. |
| title | Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2107.07386 |