On the random satisfiable process

Details On the random satisfiable process On the random satisfiable process

2008-07-27

arxiv.org/abs/0807.4326v1

Mathematics

Combinatorics

Scientific paper

In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas -- randomly permute all 2^k\binom{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 Erd\H{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.

Affiliated with

Also associated with

No associations

Rating

On the random satisfiable process does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the random satisfiable process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the random satisfiable process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-312531