The SAT-UNSAT transition for random constraint satisfaction problems
type: Item
instance of: scholarly article
title: The SAT-UNSAT transition for random constraint satisfaction problems
zbMATH Open document ID: 1185.68639
author: Nadia Creignou
author: Hervé Daudé
published in: Discrete Mathematics
publication date: 2009-06-19T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5566674
zbMATH Keywords: random structures
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: satisfiability
zbMATH Keywords: phase transition
zbMATH Keywords: sharp thresholds
MaRDI profile type: Publication
full work available at URL: j.disc.2008.04.025
OpenAlex ID: W2047532073
cites work: Q4705349
cites work: Random constraint satisfaction: A more accurate picture
cites work: Q4004078
cites work: Threshold functions
cites work: Q4228436
cites work: Generalized satisfiability problems: Minimal elements and phase transitions.
cites work: Combinatorial sharpness criterion and phase transition classification for random CSPs
cites work: Q3154710
cites work: A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
cites work: Q4952608
cites work: Supersaturated graphs and hypergraphs
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: A sharp threshold for a random constraint satisfaction problem
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: Hunting for sharp thresholds
cites work: Closure properties of constraints
cites work: The phase transition in a random hypergraph
cites work: Models for Random Constraint Satisfaction Problems
cites work: Networks of constraints: Fundamental properties and applications to picture processing
cites work: The complexity of satisfiability problems
cites work: Q4954175
DOI: 10.1016/J.DISC.2008.04.025
description: scientific article; zbMATH DE number 5566674