Threshold values of random K‐SAT from the cavity method
From MaRDI portal
Publication:5471051
DOI10.1002/rsa.20090zbMath1094.68035OpenAlexW2949171506WikidataQ61444442 ScholiaQ61444442MaRDI QIDQ5471051
Riccardo Zecchina, Stephan Mertens, Marc Mézard
Publication date: 6 June 2006
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20090
SatisfiabilityPhase TransitionAverage Case ComplexityCavity ApproachK-SATSurvey PropagationThreshold Phenomenon
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (36)
Phase transitions in discrete structures ⋮ A novel algorithm for Max Sat calling MOCE to order ⋮ The asymptotics of the clustering transition for random constraint satisfaction problems ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ On the thresholds in linear and nonlinear Boolean equations ⋮ Generating Difficult CNF Instances in Unexplored Constrainedness Regions ⋮ Why adiabatic quantum annealing is unlikely to yield speed-up ⋮ Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space ⋮ The asymptotic \(k\)-SAT threshold ⋮ CHAMP: a multipass algorithm for Max Sat based on saver variables ⋮ Threshold behaviors of a random constraint satisfaction problem with exact phase transitions ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ Threshold saturation in spatially coupled constraint satisfaction problems ⋮ Gibbs states and the set of solutions of random constraint satisfaction problems ⋮ Local search for Boolean satisfiability with configuration checking and subscore ⋮ Research on solution space of bipartite graph vertex-cover by maximum matchings ⋮ Organization mechanism and counting algorithm on vertex-cover solutions ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Captain Jack: New Variable Selection Heuristics in Local Search for SAT ⋮ The Decimation Process in Random k-SAT ⋮ On the freezing of variables in random constraint satisfaction problems ⋮ The mean field Ising model trough interpolating techniques ⋮ Pairs of SAT-assignments in random Boolean formulæ ⋮ Branching Process Approach for 2-Sat Thresholds ⋮ CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS ⋮ Probabilistic characterization of random Max \(r\)-Sat ⋮ The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$ ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ The number of solutions for random regular NAE-SAT ⋮ The number of matchings in random graphs ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ Approximate survey propagation for statistical inference ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ A model of random industrial SAT
Cites Work
This page was built for publication: Threshold values of random K‐SAT from the cavity method
