The power of choice for random satisfiability

DOI10.1007/978-3-642-40328-6_34zbMATH Open1405.68323arXiv1211.6997OpenAlexW1550219205MaRDI QIDQ2851879FDOQ2851879

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)

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.

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

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))

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)

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
• Title not available (Why is that?)

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)