Random k-sat: the limiting probability for satisfiability for moderately growing k

zbMATH Open1163.68337MaRDI QIDQ1010652FDOQ1010652

Amin Coja-Oghlan, Alan Frieze

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• A note on random \(k\)-SAT for moderately growing \(k\)
• On the critical exponents of random k‐SAT
• Bounds on threshold of regular random \(k\)-SAT
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• The number of satisfying assignments of random regular \(k\)-SAT formulas
• Theory and Applications of Satisfiability Testing
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• On the concentration of the number of solutions of random satisfiability formulas

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Combinatorial probability (60C05)

Cited In (4)

• Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• The condensation transition in random hypergraph 2-coloring

This page was built for publication: Random \(k\)-sat: the limiting probability for satisfiability for moderately growing \(k\)

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