The SAT-UNSAT transition for random constraint satisfaction problems

DOI10.1016/J.DISC.2008.04.025MaRDI QIDQ1025462zbMATH OpenOpenAlexFDO

Authors Nadia Creignou, Hervé Daudé

Publication date 19 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2008.04.025

zbMATH Keywords

constraint satisfactionphase transitionrandom structuressatisfiabilitysharp 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)

Recommendations

• Combinatorial sharpness criterion and phase transition classification for random CSPs
• scientific article; zbMATH DE number 2127760
• Threshold properties of random Boolean constraint satisfaction problems
• A sharp threshold for a random constraint satisfaction problem
• On the phase transitions of random \(k\)-constraint satisfaction problems

Cites work

• A sharp threshold for a random constraint satisfaction problem
• A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
• Closure properties of constraints
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Generalized satisfiability problems: Minimal elements and phase transitions.
• scientific article; zbMATH DE number 2127760 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• Hunting for sharp thresholds
• Models for Random Constraint Satisfaction Problems
• Networks of constraints: Fundamental properties and applications to picture processing
• Random constraint satisfaction: A more accurate picture
• Sharp thresholds of graph properties, and the k-sat problem
• Supersaturated graphs and hypergraphs
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The phase transition in a random hypergraph
• Threshold functions

Cited in

(11)

• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• SAT distributions with planted assignments and phase transitions between decision and optimization problems
• An algorithm for random signed 3-SAT with intervals
• Satisfiability thresholds beyond k-XORSAT
• scientific article; zbMATH DE number 5139164 (Why is no real title available?)
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Critical properties of the SAT/UNSAT transitions in the classification problem of structured data
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• On the thresholds in linear and nonlinear Boolean equations

This page was built for publication: The SAT-UNSAT transition for random constraint satisfaction problems

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