An efficient approach to solving random k-SAT problems

DOI10.1007/S10817-006-9025-2zbMATH Open1113.68099OpenAlexW2041982261MaRDI QIDQ877837FDOQ877837

Authors: 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

Recommendations

• scientific article; zbMATH DE number 956858
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• scientific article; zbMATH DE number 2083805
• scientific article; zbMATH DE number 1929945
• A Better Algorithm for Random k-SAT

zbMATH Keywords

automated reasoning

Mathematics Subject Classification ID

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

Cites Work

• Relations between average case complexity and approximation complexity
• Efficient CNF encoding of Boolean cardinality constraints
• A machine program for theorem-proving
• Ten challenges \textit{redux}: recent progress in propositional reasoning and search
• Title not available (Why is that?)
• The 3-XORSAT threshold.
• The efficiency of resolution and Davis-Putnam procedures
• Theory and Applications of Satisfiability Testing
• Title not available (Why is that?)
• Local search algorithms for SAT: an empirical evaluation
• Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
• Theory and Applications of Satisfiability Testing
• Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures
• Title not available (Why is that?)
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Title not available (Why is that?)
• Theory and Applications of Satisfiability Testing
• Length of prime implicants and number of solutions of random CNF formulae
• The probability of pure literals

Cited In (14)

• On the limit of branching rules for hard random unsatisfiable 3-SAT
• Theory and Applications of Satisfiability Testing
• Title not available (Why is that?)
• Branch-and-bound solves random binary IPs in poly\((n)\)-time
• Principles and Practice of Constraint Programming – CP 2004
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong Refutation Heuristics for Random k-SAT
• New models for generating hard random Boolean formulas and disjunctive logic programs
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• A collaborative approach for multi-threaded SAT solving
• Theory and Applications of Satisfiability Testing
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently

Uses Software

• kcnfs
• Chaff

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877837)