Satisfiability Decay along Conjunctions of Pseudo-Random Clauses

DOI10.1093/JIGPAL/JZL011MaRDI QIDQ3424123zbMATH OpenOpenAlexFDO

Authors Eli Shamir

Publication date 15 February 2007

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/068490abc296fef0de93d28e185355ff6741306f

zbMATH Keywords

\(k\)-SATconstraint satisfactionlearning from examplespseudorandom analysissharp thresholdsunique \(k\)-SAT representations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• A sharp threshold for a random constraint satisfaction problem
• Proof of the satisfiability conjecture for large k
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The asymptotic k-SAT threshold
• Random k-SAT: A tight threshold for moderately growing k

This page was built for publication: Satisfiability Decay along Conjunctions of Pseudo-Random Clauses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3424123)