Tricritical points in random combinatorics: the -SAT case
- 20 November 1998
- journal article
- Published by IOP Publishing in Journal of Physics A: General Physics
- Vol. 31 (46) , 9209-9217
- https://doi.org/10.1088/0305-4470/31/46/011
Abstract
The -satisfiability (SAT) problem interpolates between different classes of complexity theory and is thought to be of basic interest in understanding the onset of typical case complexity in random combinatorics. In this paper, a tricritical point in the phase diagram of the random -SAT problem is analytically computed using the replica approach and found to lie in the range . These bounds on are in agreement with previous numerical simulations and rigorous results.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Some remarks on hierarchical replica symmetry breaking in finite-connectivity systemsPhilosophical Magazine Part B, 1998
- Optimization problems and replica symmetry breaking in finite connectivity spin glassesJournal of Physics A: General Physics, 1998
- Statistical mechanics of the random-satisfiability modelPhysical Review E, 1997
- A Threshold for UnsatisfiabilityJournal of Computer and System Sciences, 1996
- Entropy of theK-Satisfiability ProblemPhysical Review Letters, 1996
- Critical Behavior in the Satisfiability of Random Boolean ExpressionsScience, 1994
- Spin glasses with p-spin interactionsNuclear Physics B, 1985
- Solvable Model of a Spin-GlassPhysical Review Letters, 1975