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 (80)

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 ⋮ Plaquette models, cellular automata, and measurement-induced criticality ⋮ Secure information hiding based on computationally intractable problems ⋮ Reduction-based MAX-3SAT with low nonlinearity and lattices under recombination ⋮ Sufficient condition for polynomial solvability of random 3-CNF formulas ⋮ 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

This page was built for publication: Critical Behavior in the Satisfiability of Random Boolean Expressions