
Computer Science 2012
Random kSAT and the Power of Two ChoicesAbstract: We study an Achlioptasprocess version of the random kSAT process: a bounded number of kclauses 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 wellstudied area of probabilistic combinatorics (Achlioptas processes) to random CSP's. In particular, while a rule to delay the 2SAT threshold was known previously, this is the first proof of a rule to shift the threshold of kSAT for k >= 3. We then propose a gap decision problem based upon this semirandom model. The aim of the problem is to investigate the hardness of the random kSAT 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.
