Behavior of heuristics and state space structure near SAT/UNSAT transition

Details Behavior of heuristics and state space structure near SAT/UNSAT transition Behavior of heuristics and state space structure near SAT/UNSAT transition

2006-01-31

arxiv.org/abs/cond-mat/0601703v1

Physics

Condensed Matter

Statistical Mechanics

12 pages, 6 figures, longer version available as MSc thesis of first author at http://biophys.physics.kth.se/docs/ardelius_the

Scientific paper

We study the behavior of ASAT, a heuristic for solving satisfiability problems by stochastic local search near the SAT/UNSAT transition. The heuristic is focused, i.e. only variables in unsatisfied clauses are updated in each step, and is significantly simpler, while similar to, walksat or Focused Metropolis Search. We show that ASAT solves instances as large as one million variables in linear time, on average, up to 4.21 clauses per variable for random 3SAT. For K higher than 3, ASAT appears to solve instances at the ``FRSB threshold'' in linear time, up to K=7.

Affiliated with

Also associated with

No associations

Rating

Behavior of heuristics and state space structure near SAT/UNSAT transition 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 Behavior of heuristics and state space structure near SAT/UNSAT transition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Behavior of heuristics and state space structure near SAT/UNSAT transition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-354171