On an online random k‐SAT model

Given n Boolean variables x 1 ,…, x n , a k ‐clause is a disjunction of k literals, where a literal is a variable or its negation. Suppose random k ‐clauses are generated one at a time and an online algorithm accepts or rejects each clause as it is generated. Our goal is to accept as many randomly generated k ‐clauses as possible with the condition that it must be possible to satisfy every clause that is accepted. When c n random k ‐clauses on n variables are given, a natural online algorithm known as Online‐Lazy accepts an expected (1 − ${{1}\over {2^{k}}}$ ) c n + a k n clauses for some constant a k . If these clauses are given offline, it is possible to do much better, (1 − ${{1}\over {2^{k}}}$ ) c n + Ω( $\sqrt{c}$ ) n can be accepted whp . The question of closing the gap between a k and Ω( $\sqrt{c}$ ) for the online version remained open. This article shows that for any k ≥ 1, any online algorithm will accept less than (1 − ${{1}\over {2^{k}}}$ ) cn + (ln 2) n k ‐clauses whp , closing the gap between the constant and Ω( $\sqrt{c}$ ). Furthermore we show that this bound is asymptotically tight as k → ∞. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008