A sharp threshold for a random constraint satisfaction problem

DOI10.1016/j.disc.2004.05.002zbMath1121.68407MaRDI QIDQ1877674

Abraham D. Flaxman

Publication date: 19 August 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Constraint satisfaction; Phase transition; Random structures; Threshold phenomena

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

06E30: Boolean functions

Related Items

A general model and thresholds for random constraint satisfaction problems, On the phase transitions of \((k, q)\)-SAT, On the phase transitions of random \(k\)-constraint satisfaction problems, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, The scaling window of the model \(d\)-\(k\)-CSP, The SAT-UNSAT transition for random constraint satisfaction problems, Many hard examples in exact phase transitions, Locally consistent constraint satisfaction problems, Sharp thresholds for constraint satisfaction problems and homomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Random 2-SAT and unsatisfiability
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Sharp thresholds of graph properties, and the $k$-sat problem
• On the 2-colorability of random hypergraphs
• Bounding the unsatisfiability threshold of random 3-SAT
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Random 2-SAT: Results and problems