Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach
Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach
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 …