On the random satisfiable process

DOI10.1017/S0963548309990356MaRDI QIDQ3552504zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Dan Vilenchik, Benny Sudakov

Publication date 22 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0807.4326

zbMATH Keywords

random satisfiable \(k\)-CNF formulas

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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

• Why almost all satisfiable k-CNF formulas are easy
• On the maximum satisfiability of random formulas
• A Better Algorithm for Random k-SAT
• A spectral technique for random satisfiable 3CNF formulas
• A better algorithm for random \(k\)-SAT

Cites work

• 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?)
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• 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)

• scientific article; zbMATH DE number 2079359 (Why is no real title available?)
• A spectral technique for random satisfiable 3CNF formulas
• Random \(k\)-SAT and the power of two choices
• Why almost all satisfiable k-CNF formulas are easy
• The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes
• Delaying satisfiability for random 2SAT
• The Kőnig graph process
• Delaying satisfiability for random 2SAT
• scientific article; zbMATH DE number 2083805 (Why is no real title available?)

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)