On the random satisfiable process

DOI10.1017/S0963548309990356zbMATH Open1214.68359arXiv0807.4326OpenAlexW2083392982MaRDI QIDQ3552504FDOQ3552504

Dan Vilenchik, Michael Krivelevich, Benny Sudakov

Publication date: 22 April 2010

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

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.

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

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

zbMATH Keywords

random satisfiable \(k\)-CNF formulas

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Some optimal inapproximability results
• Title not available (Why is that?)
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• On the size of a random maximal graph
• The random planar graph process
• Title not available (Why is that?)
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• Randomly generated intersecting hypergraphs II

Cited In (6)

• Title not available (Why is that?)
• A spectral technique for random satisfiable 3CNF formulas
• The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes
• Random k -SAT and the power of two choices
• The Kőnig graph process
• Title not available (Why is that?)

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)