An efficient approach to solving random \(k\)-SAT problems

DOI10.1007/s10817-006-9025-2zbMath1113.68099OpenAlexW2041982261MaRDI QIDQ877837

Gilles Dequen, Olivier Dubois

Publication date: 3 May 2007

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10817-006-9025-2

zbMATH Keywords

automated reasoning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

A collaborative approach for multi-threaded SAT solving ⋮ New models for generating hard random Boolean formulas and disjunctive logic programs

Uses Software

• kcnfs
• Chaff

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
• Length of prime implicants and number of solutions of random CNF formulae
• The 3-XORSAT threshold.
• Local search algorithms for SAT: an empirical evaluation
• The Efficiency of Resolution and Davis--Putnam Procedures
• Relations between average case complexity and approximation complexity
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• The probability of pure literals
• Theory and Applications of Satisfiability Testing
• A machine program for theorem-proving
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Principles and Practice of Constraint Programming – CP 2003
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: An efficient approach to solving random \(k\)-SAT problems