A sharp threshold for a random constraint satisfaction problem

DOI10.1016/j.disc.2004.05.002zbMath1121.68407OpenAlexW2164753468MaRDI 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 satisfactionPhase transitionRandom structuresThreshold phenomena

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item