Why almost all satisfiable k-CNF formulas are easy

MaRDI QIDQ3576756zbMATH OpenFDO

Authors Amin Coja-Oghlan, Michael Krivelevich, Dan Vilenchik

Publication date 2 August 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAH0107/0.html

zbMATH Keywords

SATalgorithms and data structuresmessage passing algorithmscomputational and structural complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer aspects of numerical algorithms (65Y99)

Recommendations

• On the random satisfiable process
• A Better Algorithm for Random k-SAT
• On the maximum satisfiability of random formulas
• A better algorithm for random \(k\)-SAT
• scientific article; zbMATH DE number 2083805

Cited in

(27)

• Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
• Why almost all \(k\)-colorable graphs are easy to color
• scientific article; zbMATH DE number 2090298 (Why is no real title available?)
• Optimal testing for planted satisfiability problems
• Theory and Applications of Satisfiability Testing
• Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas
• A spectral technique for random satisfiable 3CNF formulas
• A Better Algorithm for Random k-SAT
• Locally satisfiable formulas
• A short implicant of a CNF formula with many satisfying assignments
• scientific article; zbMATH DE number 1775443 (Why is no real title available?)
• Inclusion-exclusion for \(k\)-CNF formulas
• Testing satisfiability of CNF formulas by computing a stable set of points
• On the random satisfiable process
• On super strong ETH
• On the diameter of the set of satisfying assignments in random satisfiable \(k\)-CNF formulas
• Solving and sampling with many solutions: satisfiability and other hard problems
• Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas
• Sufficient condition for polynomial solvability of random 3-CNF formulas
• A combinatorial analysis for the critical clause tree
• Partial Satisfaction of k-Satisfiable Formulas
• A better algorithm for random \(k\)-SAT
• CNF satisfiability in a subspace and related problems
• Is constraint satisfaction over two variables always easy?
• On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
• A short implicant of a CNF formula with many satisfying assignments
• scientific article; zbMATH DE number 2019637 (Why is no real title available?)

Describes a project that uses

Uses Software

• Walksat

This page was built for publication: Why almost all satisfiable k-CNF formulas are easy

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