Scheme-Theoretic Approach to Computational Complexity. III. SETH

Abstract

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\ge 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.

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