Scheme-Theoretic Approach to Computational Complexity. III. SETH

2023/05/09 by Ali Çivril, Çivril, Ali
Computer Science · Mathematics · #Algorithm #Benford’s Law and Fraud Detection #Combinatorics #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational complexity theory #Computer science #Constant (computer programming) #Discrete mathematics #Mathematical analysis #Mathematics #Physics #Scheme (mathematics) #cs.CC

paper · pdf · doi:10.48550/arxiv.2305.05415

openalex publication_date 2023/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that there exist infinitely many n ∈ ℤ⁺ such that for any constant ε> 0, any deterministic algorithm to solve k-\textsfSAT for k ≥ 3 must perform at least (2^k-(3)/(2)-ε)^(n)/(k+1) operations, where n is the number of variables in the k\textsf-SAT instance.

Citations

• Scheme-theoretic Approach to Computational Complexity I. The Separation\n of P and NP

Related

• Scheme-theoretic Approach to Computational Complexity I. The Separation\n of P and NP
• On the complexity of SAT
• Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT
• Algorithm that Solves 3-SAT in Polynomial Time
• The 3-satisfiability problem