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

DOI10.1051/ita:2003014zbMath1058.68080MaRDI 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

05C80: Random graphs (graph-theoretic aspects)

68R05: Combinatorics in computer science

60C05: Combinatorial probability

Related Items

Random 2-XORSAT at the Satisfiability Threshold, Combinatorial sharpness criterion and phase transition classification for random CSPs, Random 2 XORSAT phase transition

Cites Work

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