scientific article; zbMATH DE number 1369843
From MaRDI portal
Publication:4704799
DOI<414::AID-RSA10>3.0.CO;2-G 10.1002/(SICI)1098-2418(199910/12)15:3/4<414::AID-RSA10>3.0.CO;2-GzbMath0931.68056arXivcond-mat/9910080MaRDI QIDQ4704799
Riccardo Zecchina, Lidror Troyansky, Scott Kirkpatrick, Bart Selman, Remi Monasson
Publication date: 25 November 1999
Full work available at URL: https://arxiv.org/abs/cond-mat/9910080
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
A Model for Phase Transition of Random Answer-Set Programs, On preprocessing techniques and their impact on propositional model counting, A sharp threshold in proof complexity yields lower bounds for satisfiability search, The phase transition in random horn satisfiability and its algorithmic implications, On threshold properties of \(k\)-SAT: An additive viewpoint, A note on the complexity of Boolean concepts, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, The asymptotics of the clustering transition for random constraint satisfaction problems, An efficient approach to solving random \(k\)-SAT problems, String matching and 1d lattice gases, Boosting quantum annealer performance via sample persistence, Minimal sets on propositional formulae. Problems and reductions, Random logic programs: Linear model, Phase transitions in theq-coloring of random hypergraphs, Phase transitions of contingent planning problem, Computational complexity of auditing finite attributes in statistical databases, The scaling window of the 2-SAT transition, Random subcubes as a toy model for constraint satisfaction problems, The large deviations of the whitening process in random constraint satisfaction problems, Visualizing SAT instances and runs of the DPLL algorithm, Recognizing frozen variables in constraint satisfaction problems, Numerical results for spin glass ground states on Bethe lattices: Gaussian bonds, Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances, 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, Unnamed Item, Statistical mechanics methods and phase transitions in optimization problems, Rigorous results for random (\(2+p)\)-SAT, Lower bounds for random 3-SAT via differential equations, Frozen development in graph coloring, Bounding the scaling window of random constraint satisfaction problems, Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles, The set of solutions of random XORSAT formulae, Statistical and algebraic analysis of a family of random Boolean equations, On the Hardness of SAT with Community Structure, k-SAT Is No Harder Than Decision-Unique-k-SAT, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, When does the giant component bring unsatisfiability?, Biased landscapes for random constraint satisfaction problems, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Spines of random constraint satisfaction problems: definition and connection with computational complexity
Cites Work
- Unnamed Item
- Optimization by Simulated Annealing
- A threshold for unsatisfiability
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Searching for backbones -- an efficient parallel algorithm for the traveling salesman problem
- The Sherrington-Kirkpatrick model: A challenge for mathematicians
- Renormalization group theory: Its basis and formulation in statistical physics
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Random-energy model: An exactly solvable model of disordered systems
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Optimization problems and replica symmetry breaking in finite connectivity spin glasses
- Entropy of theK-Satisfiability Problem
- Tail bounds for occupancy and the satisfiability threshold conjecture
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Tricritical points in random combinatorics: the -SAT case
- Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition
- A Computing Procedure for Quantification Theory
- The complexity of theorem-proving procedures
