Random k ‐SAT and the power of two choices

We study an Achlioptas‐process version of the random k ‐SAT process: a bounded number of k ‐clauses are drawn uniformly at random at each step, and exactly one added to the growing formula according to a particular rule. We prove the existence of a rule that shifts the satisfiability threshold. This extends a well‐studied area of probabilistic combinatorics (Achlioptas processes) to random CSP's. In particular, while a rule to delay the 2‐SAT threshold was known previously, this is the first proof of a rule to shift the threshold of k ‐SAT for k ≥ 3 . We then propose a gap decision problem based upon this semi‐random model. The aim of the problem is to investigate the hardness of the random k ‐SAT decision problem, as opposed to the problem of finding an assignment or certificate of unsatisfiability. Finally, we discuss connections to the study of Achlioptas random graph processes. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 163–173, 2015