Combinatorial sharpness criterion and phase transition classification for random CSPs

DOI10.1016/J.IC.2004.01.002MaRDI QIDQ598196zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Hervé Daudé

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

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

Recommendations

• The SAT-UNSAT transition for random constraint satisfaction problems
• scientific article; zbMATH DE number 2127760
• A sharp threshold for a random constraint satisfaction problem
• Threshold properties of random Boolean constraint satisfaction problems
• On the phase transitions of random \(k\)-constraint satisfaction problems

Cites work

• scientific article; zbMATH DE number 4082595 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• A threshold for unsatisfiability
• Complexity classifications of Boolean constraint satisfaction problems
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Models for Random Constraint Satisfaction Problems
• Poisson convergence and Poisson processes with applications to random graphs
• Random constraint satisfaction: Flaws and structure
• Satisfiability threshold for random XOR-CNF formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
• The 3-XORSAT threshold.
• The complexity of satisfiability problems

Cited in

(16)

• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Pairs of SAT-assignments in random Boolean formulæ
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• A general model and thresholds for random constraint satisfaction problems
• Threshold properties of random Boolean constraint satisfaction problems
• Many hard examples in exact phase transitions
• The SAT-UNSAT transition for random constraint satisfaction problems
• Super solutions of random instances of satisfiability
• An algorithm for random signed 3-SAT with intervals
• When does the giant component bring unsatisfiability?
• Spines of random constraint satisfaction problems: definition and connection with computational complexity
• On the phase transitions of random \(k\)-constraint satisfaction problems
• A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
• The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
• A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
• scientific article; zbMATH DE number 2127760 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598196)