The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability

Thomas Bläsius, Tobias Friedrich, Andreas Göbel +2

Satisfiability is considered the canonical NP-complete problem and is used as a starting point for hardness reductions in theory, while in practice heuristic SAT solving algorithms…