Hiding solutions in random satisfiability problems: A statistical mechanics approach

Details Hiding solutions in random satisfiability problems: A statistical mechanics approach Hiding solutions in random satisfiability problems: A statistical mechanics approach

2001-11-09

arxiv.org/abs/cond-mat/0111153v2

Phys. Rev. Lett. 88, 188701 (2002)

Physics

Condensed Matter

Disordered Systems and Neural Networks

5 pages, 4 figures, revised version to app. in PRL

Scientific paper

10.1103/PhysRevLett.88.188701

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 (3SAT). 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.

Affiliated with

Also associated with

No associations

Rating

Hiding solutions in random satisfiability problems: A statistical mechanics approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hiding solutions in random satisfiability problems: A statistical mechanics approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hiding solutions in random satisfiability problems: A statistical mechanics approach will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-539123