Combinatorial sharpness criterion and phase transition classification for random CSPs

DOI10.1016/J.IC.2004.01.002zbMATH Open1085.68151OpenAlexW2088486516MaRDI QIDQ598196FDOQ598196

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

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

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)

Cites Work

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

Cited In (16)

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

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)