The #ETH is False, #k-SAT is in Sub-Exponential Time

2021/02/03 by Giorgio Camerani, Camerani, Giorgio
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #F.2.2 #FOS: Computer and information sciences #G.2.1 #I.1.2 #I.2.8 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2102.02624

openalex publication_date 2021/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We orchestrate a randomized algorithm for #k-SAT which counts the exact number of satisfying assignments in 2^o(n) time. The existence of such algorithm signifies that the #ETH is hereby refuted, and so are ⊕ETH, ETH, #SETH, ⊕SETH and SETH.

Citations

• The Long, the Short and the Random

Related

• Super Strong ETH is False for Random k-SAT
• The Long, the Short and the Random
• A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
• A Full Derandomization of Schoening's k-SAT Algorithm
• Simpler Partial Derandomization of PPSZ for k-SAT