Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability

DOI10.1051/ita:2003014zbMath1058.68080OpenAlexW2151434544MaRDI QIDQ4825479

Nadia Creignou, Hervé Daudé

Publication date: 28 October 2004

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92718

zbMATH Keywords

threshold phenomenon

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorics in computer science (68R05) Combinatorial probability (60C05)

Related Items (5)

Combinatorial sharpness criterion and phase transition classification for random CSPs ⋮ Random 2 XORSAT phase transition ⋮ The Satisfiability Threshold fork-XORSAT ⋮ 2-Xor revisited: satisfiability and probabilities of functions ⋮ Random 2-XORSAT at the Satisfiability Threshold

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• Poisson convergence and Poisson processes with applications to random graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Satisfiability threshold for random XOR-CNF formulas
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Almost all graphs with 1.44n edges are 3-colorable
• Hypercycles in a random hypergraph
• Sharp thresholds of graph properties, and the $k$-sat problem
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• The complexity of satisfiability problems

This page was built for publication: Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability