Why almost all satisfiable k-CNF formulas are easy

zbMATH Open1192.68949MaRDI QIDQ3576756FDOQ3576756

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

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

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)

Cited In (27)

• Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
• Title not available (Why is that?)
• Why almost all \(k\)-colorable graphs are easy to color
• Theory and Applications of Satisfiability Testing
• Optimal testing for planted satisfiability problems
• 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
• Title not available (Why is that?)
• 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
• Solving and sampling with many solutions: satisfiability and other hard problems
• On the diameter of the set of satisfying assignments in random satisfiable \(k\)-CNF formulas
• Sufficient condition for polynomial solvability of random 3-CNF formulas
• Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas
• A better algorithm for random \(k\)-SAT
• Partial Satisfaction of k-Satisfiable Formulas
• A combinatorial analysis for the critical clause tree
• 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
• Title not available (Why is that?)

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)