Threshold values of Random K-SAT from the cavity method
| dc.creator | Mertens, Stephan | |
| dc.creator | Mezard, Marc | |
| dc.creator | Zecchina, Riccardo | |
| dc.date | 2003-09-12 | |
| dc.date | 2005-02-24 | |
| dc.date.accessioned | 2026-07-07T03:20:19Z | |
| dc.date.available | 2026-07-07T03:20:19Z | |
| dc.description | Using the cavity equations of \cite{mezard:parisi:zecchina:02,mezard:zecchina:02}, we derive the various threshold values for the number of clauses per variable of the random $K$-satisfiability problem, generalizing the previous results to $K \ge 4$. We also give an analytic solution of the equations, and some closed expressions for these thresholds, in an expansion around large $K$. The stability of the solution is also computed. For any $K$, the satisfiability threshold is found to be in the stable region of the solution, which adds further credit to the conjecture that this computation gives the exact satisfiability threshold. | |
| dc.description | 38 pages; extended explanations and derivations; this version is going to appear in Random Structures & Algorithms | |
| dc.identifier | https://arxiv.org/abs/cs/0309020 | |
| dc.identifier | http://arxiv.org/abs/cs/0309020 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31784 | |
| dc.subject | Computational Complexity | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.0; G.2.0 | |
| dc.title | Threshold values of Random K-SAT from the cavity method | |
| dc.type | text |