Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach
- 18 April 2002
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 88 (18) , 188701
Abstract
A major problem in evaluating stochastic local search algorithms for NP-complete problems is the need for a systematic generation of hard test instances having previously known properties of the optimal solutions. On the basis of statistical mechanics results, we propose random generators of hard and satisfiable instances for the 3-satisfiability problem. The design of the hardest problem instances is based on the existence of a first order ferromagnetic phase transition and the glassy nature of excited states. The analytical predictions are corroborated by numerical results obtained from complete as well as stochastic local algorithms.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Exact Solutions for Diluted Spin Glasses and Optimization ProblemsPhysical Review Letters, 2001
- The Bethe lattice spin glass revisitedThe European Physical Journal B, 2001
- Simplest randomK-satisfiability problemPhysical Review E, 2001
- Local Search Algorithms for SAT: An Empirical EvaluationJournal of Automated Reasoning, 2000
- A variational description of the ground state structure in random satisfiability problemsThe European Physical Journal B, 2000
- Determining computational complexity from characteristic ‘phase transitions’Nature, 1999
- Statistical mechanics of the random-satisfiability modelPhysical Review E, 1997
- Hard instance generation for SATLecture Notes in Computer Science, 1997
- Entropy of theK-Satisfiability ProblemPhysical Review Letters, 1996
- Optimization by Simulated AnnealingScience, 1983