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 (3-SAT). 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. PACS numbers: 89.20.Ff, 02.60.Pn, 05.70.Fh, 75.10.Nr In natural sciences and in artificial systems, there exist many problems whose solution requires computational resources growing exponentially with the number of variables N needed for their encoding. Concrete examples are optimization and cryptographic problems in computer science, glassy systems and random structures in physics and chemistry, random graphs in mathematics, and scheduling problems in real-world applications. Having fast and powerful algorithms for the resolution of these problems is of primary relevance for their theoretical study as well as for applications. The evaluation of such algorithms is based on the availability of hard benchmarks, having the following properties: They provide problem instances, with a given known solution, in a fast way (e.g. linear in N ), but the resolution of an instance takes a time exponential in N for any known algorithm. So the best algorithms can be easily selected. In this letter we propose a new generator of hard and solvable test instances, having all the properties listed above. It is based on a NP-complete problem [1] -namely 3-satisfiability (3-SAT). The main idea for the construction of such hard and solvable problems is very simple: to hide a known solution within a multitude of coexisting random meta-stable configurations which constitute dynamical barriers. In the physical approach based on a mapping from 3-SAT to a spin glass model [2] , such random configurations correspond to glassy states [3] . It is to be noted, however, that many previous attempts to implement this idea were unsuccessful, because the random structure was usually easy to remove, or knowledge that a solution has been forced can be exploited to find it. In the instances we propose, instead, the presence of a known solution does not alter the structure of the glassy state, which confuses the solver and makes the problem hard. As an important application of these ideas to cryptography [4], random one-way functions are provided: A given message, e.g. a password, can be coded in a 3-SAT formula and thus verified efficiently, but decoding it is extremely time-consuming. We use the framework of the typical-case computational complexity [5, 6] . There, the study of random 3-SAT problems has played a major role. A random 3-SAT formula F consists of M logical clauses {C µ } µ=1,...,M over a set of N Boolean variables {x i = 0, 1} i=1,...,N , with 0=FALSE and 1=TRUE. Every clause consists of three randomly chosen Boolean variables which are connected by logical OR operations (∨) and appear negated with probability 1/2, e.g. C µ = (x i ∨ x j ∨ x k ). In F the clauses are connected by logical AND operations (∧), F = M µ=1 C µ , so that all clauses have to be satisfied simultaneously in order to satisfy the formula. A satisfying logical assignment of the x i is also called a solution of F . The random 3-SAT model was found to undergo a SAT/UNSAT phase transition [7] at a critical ratio α c = M/N ≃ 4.25 (N ≫ 1): Below α c , almost all formulae are satisfiable, while beyond almost all formulae do not show any solution. At this threshold, a strong exponential peak in the typical (median) cost for finding solutions by the best known algorithms appears. Problem instances generated close to it form a natural test bed for the optimization of heuristic search algorithms. However, satisfiable and unsatisfiable instances coexist in this region. Many algorithms of practical interest [8] are based on incomplete stochastic local search procedures, as e.g. simulated annealing [9] and the walk-SAT algorithm [10] . These algorithms stop once they have found a solution, but they have no way to disentangle, in polynomial time in N , if a formula is unsatisfiable or just hard to solve. It is thus very important to generate benchmarks which are satisfiable and for which the algorithmic proof of this satisfiability takes an exponential time in N. In this Letter, we propose simple and fast generators of such benchmark problems. The main ideas are inspired by physical requirements, and exploit the presumed hard-
Another approach, quite easy to implement, has also been proposed by REF : any 3-SAT instance is forced to be satisfiable by forbidding the clauses violated by both an assignment and its complement.
Hiding solutions in random satisfiability problems: A statistical mechanics approach
Phys. Rev. Lett. 88, 188701 (2002)
Medicine Physics Computer Science