Probabilistic threshold conjecture for -SAT games
Probabilistic threshold conjecture for -SAT games
Let be the -uniform clause set on Boolean variables, and let be the family of satisfiable clause sets. Consider the Waiter–Client and Client–Waiter -SAT games, and denote their threshold biases by and , respectively.
-SAT threshold conjecture. The threshold biases satisfy
The conjecture predicts the probabilistically suggested asymptotic threshold for both game orientations. The paper proves the threshold only up to exponential and polynomial factors in for the Waiter–Client and Client–Waiter versions, respectively, so the exact asymptotic remains open.
Sources & referencesView supporting material
Primary source
Wei En Tan, “Waiter-Client and Client-Waiter colourability games on a k-uniform hypergraph and the k-SAT game”, arXiv:1607.02258 (2016).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.