Approximating satisfiability transition by suppressing fluctuations

Details Approximating satisfiability transition by suppressing fluctuations Approximating satisfiability transition by suppressing fluctuations

2004-03-17

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

Physics

Condensed Matter

Disordered Systems and Neural Networks

31 pages, 6 figures

Scientific paper

Using methods and ideas from statistical mechanics, we propose a simple method for obtaining rigorous upper bounds for satisfiability transition in random boolean expressions composed of N variables and M clauses with K variables per clause. Determining the location of satisfiability threshold $\alpha_c=M/N$ for a number of difficult combinatorial problems is a major open problem in the theory of random graphs. The method is based on identification of the core -- a subexpression (subgraph) that has the same satisfiability properties as the original expression. We formulate self-consistency equations that determine macroscopic parameters of the core and compute an improved annealing bound. We illustrate the method for three sample problems: K-XOR-SAT, K-SAT and positive 1-in-K-SAT.

Affiliated with

Also associated with

No associations

Rating

Approximating satisfiability transition by suppressing fluctuations 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 Approximating satisfiability transition by suppressing fluctuations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating satisfiability transition by suppressing fluctuations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-151707