Random k‐SAT and the power of two choices 1. Issue 1 (19th March 2014)

• Record Type: Journal Article
• Authors: Perkins, Will
• Is Part Of: Random structures & algorithms. Volume 47:Issue 1(2015)
• Page Start: 163
• Page End: 173
• Publication Date: 2014-03-19
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20534
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>ABSTRACT</title> <p>We study an Achlioptas‐process version of the random <italic>k</italic>‐SAT process: a bounded number of <italic>k</italic>‐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 <italic>k</italic>‐SAT for <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqkn57" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20534:rsa20534-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math></alternatives></inline-formula>. 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 <italic>k</italic>‐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</p> </abstract>