Abstract
We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio α of clauses to variables less than a threshold α c are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below α c , where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability.
Keywords
SatisfiabilityBenchmark (surveying)Boolean satisfiability problemClass (philosophy)MetastabilityMaximum satisfiability problemComputer scienceMathematicsCombinatoricsDiscrete mathematicsAlgorithmBoolean functionPhysicsArtificial intelligence
Affiliated Institutions
Related Publications
Barren plateaus in quantum neural network training landscapes
Many experimental proposals for noisy intermediate scale quantum devices involve training a parameterized quantum circuit with a classical optimization loop. Such hybrid quantum...
Modified Randomization Tests for Nonparametric Hypotheses
Suppose $X_1, \\cdots, X_m, Y_1, \\cdots, Y_n$ are $m + n = N$ independent random variables, the $X$'s identically distributed and the $Y$'s identically distributed, each with a...
Robust Estimation of a Location Parameter
This paper contains a new approach toward a theory of robust estimation; it treats in detail the asymptotic theory of estimating a location parameter for contaminated normal dis...
Publication Info
- Year
- 2002
- Type
- article
- Volume
- 297
- Issue
- 5582
- Pages
- 812-815
- Citations
- 1038
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1038
OpenAlex
Cite This
Marc Mézard,
Giorgio Parisi,
Riccardo Zecchina
(2002).
Analytic and Algorithmic Solution of Random Satisfiability Problems.
Science
, 297
(5582)
, 812-815.
https://doi.org/10.1126/science.1073287
Identifiers
- DOI
- 10.1126/science.1073287