Combinatorial sharpness criterion and phase transition classification for random CSPs
From MaRDI portal
Publication:598196
DOI10.1016/j.ic.2004.01.002zbMath1085.68151MaRDI QIDQ598196
Publication date: 6 August 2004
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2004.01.002
Coarse thresholds; Constraint satisfaction problems; Phase transition classification; Sharp thresholds
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
A general model and thresholds for random constraint satisfaction problems, A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming, On the phase transitions of random \(k\)-constraint satisfaction problems, Spines of random constraint satisfaction problems: definition and connection with computational complexity, The SAT-UNSAT transition for random constraint satisfaction problems, When does the giant component bring unsatisfiability?, The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas, Many hard examples in exact phase transitions, Pairs of SAT-assignments in random Boolean formulæ, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Threshold properties of random Boolean constraint satisfaction problems, An algorithm for random signed 3-SAT with intervals, Super Solutions of Random Instances of Satisfiability, Sharp thresholds for constraint satisfaction problems and homomorphisms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A threshold for unsatisfiability
- Poisson convergence and Poisson processes with applications to random graphs
- Generalized satisfiability problems: Minimal elements and phase transitions.
- The 3-XORSAT threshold.
- Satisfiability threshold for random XOR-CNF formulas
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Sharp thresholds of graph properties, and the $k$-sat problem
- Models for Random Constraint Satisfaction Problems
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- The complexity of satisfiability problems
- Random constraint satisfaction: Flaws and structure