The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)

DOI10.1090/S0894-0347-04-00464-3zbMath1093.68075arXivcs/0305009OpenAlexW2145098470MaRDI QIDQ4821034

Publication date: 7 October 2004

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0305009

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Discrete mathematics in relation to computer science (68R99)

Related Items

Waiter-client and client-waiter colourability and $k$-SAT games, Phase transitions in discrete structures, On the solution‐space geometry of random constraint satisfaction problems, Lower and Upper Bounds for Random Mimimum Satisfiability Problem, On the number of circuits in random graphs, The Number of Satisfying Assignments of Random Regulark-SAT Formulas, Random $\mathbb{Z}^d$-shifts of finite type, An algorithm for random signed 3-SAT with intervals, Random Instances of Problems in NP – Algorithms and Statistical Physics, Regular random $k$-SAT: Properties of balanced formulas, On the concentration of the number of solutions of random satisfiability formulas, On the thresholds in linear and nonlinear Boolean equations, Free energy subadditivity for symmetric random Hamiltonians, The mean field traveling salesman and related problems, Harnessing the Bethe free energy, The number of satisfying assignments of random 2‐SAT formulas, The discrepancy of random rectangular matrices, Digital collections of examples in mathematical sciences, One-step replica symmetry breaking of random regular NAE-SAT. II, Analysis of local search landscapes for $k$-SAT instances, The asymptotic $k$-SAT threshold, CHAMP: a multipass algorithm for Max Sat based on saver variables, A tighter upper bound for random MAX $2$-SAT, Go-MOCE: greedy order method of conditional expectations for Max Sat, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities, On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT, On the Lower Bounds of Random Max 3 and 4-SAT, The large deviations of the whitening process in random constraint satisfaction problems, Constructing concrete hard instances of the maximum independent set problem, A NEW UPPER BOUND FOR RANDOM (2 + p)-SAT BY FLIPPING TWO VARIABLES, The Decimation Process in Random k-SAT, Charting the replica symmetric phase, On the phase transitions of $(k, q)$-SAT, On the lower bounds of random Max 3 and 4-SAT, Pairs of SAT-assignments in random Boolean formulæ, Optimal testing for planted satisfiability problems, Spin systems on Bethe lattices, Branching Process Approach for 2-Sat Thresholds, Solution clustering in random satisfiability, Unnamed Item, Satisfiability threshold for random regular \textsc{nae-sat}, Probabilistic characterization of random Max $r$-Sat, The structure of the set of satisfying assignments for a random $k$-CNF, Geometrical organization of solutions to random linear Boolean equations, The set of solutions of random XORSAT formulae, The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$, Independent Sets in Random Graphs from the Weighted Second Moment Method, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, The condensation transition in random hypergraph 2-coloring, The replica symmetric phase of random constraint satisfaction problems, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Belief propagation on the random $k$-SAT model, Using the method of conditional expectations to supply an improved starting point for CCLS, Streamlining variational inference for constraint satisfaction problems, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Unnamed Item, On the hardness of solving edge matching puzzles as SAT or CSP problems, Walksat Stalls Well Below Satisfiability, A model of random industrial SAT

Cites Work