Approximating satisfiability transition by suppressing fluctuations
| dc.creator | Knysh, S. | |
| dc.creator | Smelyanskiy, V. N. | |
| dc.creator | Morris, R. D. | |
| dc.date | 2004-03-17 | |
| dc.date.accessioned | 2026-07-07T02:56:58Z | |
| dc.date.available | 2026-07-07T02:56:58Z | |
| dc.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. | |
| dc.description | 31 pages, 6 figures | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0403416 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0403416 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/23543 | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.subject | Statistical Mechanics | |
| dc.title | Approximating satisfiability transition by suppressing fluctuations | |
| dc.type | text |