Scheme-Theoretic Approach to Computational Complexity. III. SETH
| Autor: | Çivril, Ali |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We show that there exist infinitely many $n \in \mathbb{Z}^+$ such that for any constant $\epsilon > 0$, any deterministic algorithm to solve $k$-\textsf{SAT} for $k \geq 3$ must perform at least $(2^{k-\frac{3}{2}-\epsilon})^{\frac{n}{k+1}}$ operations, where $n$ is the number of variables in the $k$\textsf{-SAT} instance. Comment: 6 pages. Updated the definitions according to the first paper in the series |
| Databáze: | arXiv |
| Externí odkaz: |
|