Recognizing more random unsatisfiable 3-SAT instances efficiently

DOI10.1016/S1571-0653(04)00461-5zbMath1179.68143MaRDI QIDQ3439113

André Lanka, Andreas Goerdt

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (3)

On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Short propositional refutations for dense random 3CNF formulas

Cites Work

• The eigenvalues of random symmetric matrices
• Relations between average case complexity and approximation complexity
• Sharp thresholds of graph properties, and the $k$-sat problem
• Spectral techniques applied to sparse random graphs
• Fundamentals of Computation Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Recognizing more random unsatisfiable 3-SAT instances efficiently