The impact of heterogeneity and geometry on the proof complexity of random satisfiability
The impact of heterogeneity and geometry on the proof complexity of random satisfiability
Abstract 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 can solve largeāscale industrial SAT instances very efficiently. This disparity between theory and practice is believed to be a result of inherent properties ā¦