Critical Behavior in the Satisfiability of Random Boolean Expressions

DOI10.1126/science.264.5163.1297zbMath1226.68097OpenAlexW1968198053WikidataQ52376945 ScholiaQ52376945MaRDI QIDQ3101335

Scott Kirkpatrick, Bart Selman

Publication date: 28 November 2011

Published in: Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1126/science.264.5163.1297

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) Boolean functions (06E30)

Related Items

GD-SAT model and crossover line, Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas, Sharp thresholds of graph properties, and the $k$-sat problem, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, A user authentication protocol based on the intractability of the 3-coloring problem, Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study, Critical Density Thresholds in Distributed Wireless Networks, A sharp threshold in proof complexity yields lower bounds for satisfiability search, The phase transition in random horn satisfiability and its algorithmic implications, Random subcube intersection graphs. I: Cliques and covering, Gradient descent dynamics and the jamming transition in infinite dimensions, PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, Tutorial series on brain-inspired computing. V: Statistical mechanics of communication and computation, On the concentration of the number of solutions of random satisfiability formulas, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, Unnamed Item, Combinatorial sharpness criterion and phase transition classification for random CSPs, Computational complexity of the landscape. I., String matching and 1d lattice gases, Resolving Braess's paradox in random networks, Tensor network contractions for \#SAT, On the thresholds in linear and nonlinear Boolean equations, Phase transitions and the search problem, Generating hard satisfiability problems, Experimental results on the crossover point in random 3-SAT, An empirical study of phase transitions in binary constraint satisfaction problems, Locating the phase transition in binary constraint satisfaction problems, Hard random 3-SAT problems and the Davis-Putnam procedure, Implicates and prime implicates in random 3-SAT, Critical behavior in the computational cost of satisfiability testing, Problem structure heuristics and scaling behavior for genetic algorithms, The TSP phase transition, Accelerating a continuous-time analog SAT solver using GPUs, Biased random k‐SAT, Generalized satisfiability problems: Minimal elements and phase transitions., The asymptotic \(k\)-SAT threshold, Threshold behaviors of a random constraint satisfaction problem with exact phase transitions, (2+\(f\)(\(n\)))-SAT and its properties., On the average similarity degree between solutions of random \(k\)-SAT and random CSPs., Manipulation can be hard in tractable voting systems even for constant-sized coalitions, Modelling the dynamics of stochastic local search on \(k\)-SAT, Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One, Phase Transition for Maximum Not-All-Equal Satisfiability, Error catastrophe for viruses infecting cells: analysis of the phase transition in terms of error classes, The scaling window of the 2-SAT transition, Random subcubes as a toy model for constraint satisfaction problems, Local search for Boolean satisfiability with configuration checking and subscore, On the quantum spin glass transition on the Bethe lattice, Constructing concrete hard instances of the maximum independent set problem, Pairs of SAT-assignments in random Boolean formulæ, Efficient branch-and-bound algorithms for weighted MAX-2-SAT, The satisfiability threshold for random linear equations, Physics and complexity, Phase transition and finite-size scaling in the vertex-cover problem, Quantum optimization, On the satisfiability threshold of formulas with three literals per clause, Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT, Statistical mechanics methods and phase transitions in optimization problems, Bounding the scaling window of random constraint satisfaction problems, Coreduction homology algorithm, Secure information hiding based on computationally intractable problems, On the survey-propagation equations in random constraint satisfiability problems, An Experimental Study of Operator Choices in the $$(1+(\lambda ,\lambda ))$$ Genetic Algorithm, A hard-sphere model on generalized Bethe lattices: dynamics, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, Random matrix model of adiabatic quantum computing, A new method for testing decision procedures in modal logics, Complexity-theoretic models of phase transitions in search problems, Delaying satisfiability for random 2SAT, A framework for structured quantum search., Entropy of theK-Satisfiability Problem, PhysComp96. Proceedings of the 4th workshop on physics and computation, Boston, MA, USA, November 22--24, 1996, SAT distributions with planted assignments and phase transitions between decision and optimization problems, SAT Distributions with Phase Transitions between Decision and Optimization Problems, An efficient local search method for random 3-satisfiability