Combinatorial sharpness criterion and phase transition classification for random CSPs

DOI10.1016/j.ic.2004.01.002zbMath1085.68151OpenAlexW2088486516MaRDI QIDQ598196

Hervé Daudé, Nadia Creignou

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

zbMATH Keywords

Coarse thresholdsConstraint satisfaction problemsPhase transition classificationSharp thresholds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (15)

Many hard examples in exact phase transitions ⋮ Super Solutions of Random Instances of Satisfiability ⋮ An algorithm for random signed 3-SAT with intervals ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming ⋮ Pairs of SAT-assignments in random Boolean formulæ ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ 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 ⋮ 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 ⋮ Spines of random constraint satisfaction problems: definition and connection with computational complexity

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Combinatorial sharpness criterion and phase transition classification for random CSPs