Abstract: In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas -- randomly permute all 2^k�inom{n}{k} possible clauses over the variables x_1, ..., x_n, and starting from the empty formula, go over the clauses one by one, including each new clause as you go along if after its addition the formula remains satisfiable. We study the evolution of this process, namely the distribution over formulas obtained after scanning through the first m clauses (in the random permutation's order). Random processes with conditioning on a certain property being respected are widely studied in the context of graph properties. This study was pioneered by Ruci'nski and Wormald in 1992 for graphs with a fixed degree sequence, and also by ErdH{o}s, Suen, and Winkler in 1995 for triangle-free and bipartite graphs. Since then many other graph properties were studied such as planarity and H-freeness. Thus our model is a natural extension of this approach to the satisfiability setting. Our main contribution is as follows. For m geq cn, c=c(k) a sufficiently large constant, we are able to characterize the structure of the solution space of a typical formula in this distribution. Specifically, we show that typically all satisfying assignments are essentially clustered in one cluster, and all but e^{-Omega(m/n)} n of the variables take the same value in all satisfying assignments. We also describe a polynomial time algorithm that finds with high probability a satisfying assignment for such formulas.
Recommendations
Cites work
- A Spectral Technique for Coloring Random 3-Colorable Graphs
- Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
- scientific article; zbMATH DE number 48812 (Why is no real title available?)
- scientific article; zbMATH DE number 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 3251924 (Why is no real title available?)
- On the size of a random maximal graph
- Randomly generated intersecting hypergraphs II
- Sharp thresholds of graph properties, and the k-sat problem
- Some optimal inapproximability results
- The random planar graph process
Cited in
(9)- Delaying satisfiability for random 2SAT
- Random k-SAT and the power of two choices
- The Kőnig graph process
- A spectral technique for random satisfiable 3CNF formulas
- Why almost all satisfiable k-CNF formulas are easy
- Delaying satisfiability for random 2SAT
- scientific article; zbMATH DE number 2079359 (Why is no real title available?)
- scientific article; zbMATH DE number 2083805 (Why is no real title available?)
- The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes
This page was built for publication: On the random satisfiable process
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3552504)
