Combinatorial sharpness criterion and phase transition classification for random CSPs

DOI10.1016/j.ic.2004.01.002zbMath1085.68151MaRDI 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 thresholds; Constraint satisfaction problems; Phase transition classification; Sharp thresholds

Mathematics Subject Classification ID

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