The power of choice for random satisfiability

DOI10.1007/978-3-642-40328-6_34MaRDI QIDQ2851879zbMATH OpenOpenAlexFDO

Authors Varsha Dani, Thomas P. Hayes, Cristopher Moore, J. Díaz

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.6997

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We consider Achlioptas processes for k-SAT formulas. We create a semi-random formula with n variables and m clauses, where each clause is a choice, made on-line, between two or more uniformly random clauses. Our goal is to delay the satisfiability/unsatisfiability transition, keeping the formula satisfiable up to densities m/n beyond the satisfiability threshold alpha_k for random k-SAT. We show that three choices suffice to raise the threshold for any k >= 3, and that two choices suffice for all 3 <= k <= 25. We also show that two choices suffice to lower the threshold for all k >= 3, making the formula unsatisfiable at a density below alpha_k.

Recommendations

• Random \(k\)-SAT and the power of two choices
• Delaying satisfiability for random 2SAT
• Delaying satisfiability for random 2SAT
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))

Cited in

(7)

• Random \(k\)-SAT and the power of two choices
• Delaying satisfiability for random 2SAT
• Waiter-client and client-waiter colourability and \(k\)-SAT games
• Delaying satisfiability for random 2SAT
• On the power of choice for Boolean functions
• Power-of-d-Choices with Memory: Fluid Limit and Optimality
• scientific article; zbMATH DE number 2083805 (Why is no real title available?)

This page was built for publication: The power of choice for random satisfiability

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