Approximating satisfiability transition by suppressing fluctuations

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 $α_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.
31 pages, 6 figures

Keywords

Disordered Systems and Neural Networks, Statistical Mechanics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/23543

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cond-mat/0403416
 http://arxiv.org/abs/cond-mat/0403416

Collections

arXiv