The Long, the Short and the Random

2020/11/03 by Giorgio Camerani, Camerani, Giorgio · 1 citation
Computer Science · #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.1.3 #F.2.2 #FOS: Computer and information sciences #G.2.1 #I.1.2 #I.2.8

paper · pdf · doi:10.48550/arxiv.2011.01649

openalex publication_date 2020/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We furnish solid evidence, both theoretical and empirical, towards the existence of a deterministic algorithm for random sparse #Ω(log n)-SAT instances, which computes the exact counting of satisfying assignments in sub-exponential time. The algorithm uses a nice combinatorial property that every CNF formula has, which relates its number of unsatisfying assignments to the space of its monotone sub-formulae.

Citations

• Which Problems Have Strongly Exponential Complexity?

Cited by

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

Related

• Faster Random k-CNF Satisfiability
• An Improved Algorithm for Sparse Instances of SAT
• Counting good truth assignments of random k-SAT formulae
• Fast sampling and counting k-SAT solutions in the local lemma regime
• The number of satisfying assignments of random regular k-SAT formulas