Premium
Random k ‐SAT and the power of two choices
Author(s) -
Perkins Will
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20534
Subject(s) - random graph , mathematics , probabilistic logic , satisfiability , discrete mathematics , combinatorics , bounded function , graph , statistics , mathematical analysis
ABSTRACT 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