Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Bounds on Threshold of Regular Random k-SAT
KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Communication Theory.
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
KTH, School of Electrical Engineering (EES), Communication Theory. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-7182-9543
KTH, School of Electrical Engineering (EES), Communication Theory. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0002-7926-5081
2010 (English)In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 6175, 264-277 p.Article in journal (Refereed) Published
Abstract [en]

We consider the regular model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad et. al. in [6]. In [6], it was shown that the threshold for regular random 2-SAT is equal to unity. Also, upper and lower bound on the threshold for regular random 3-SAT were derived. Using the first moment method, we derive an upper bound on the threshold for regular random k-SAT for any k >= 3 and show that for large k the threshold is upper bounded by 2(k) ln(2). We also derive upper bounds on the threshold for Not-All-Equal (NAE) satisfiability for k >= 3 and show that for large k, the NAE-satisfiability threshold is upper bounded by 2(k-1) ln(2). For both satisfiability and NAE-satisfiability, the obtained upper bound matches with the corresponding bound for the uniform model of formula generation [9, 1]. For the uniform model, in a series of break through papers Achlioptas, Moore, and Peres showed that a careful application of the second moment method yields a significantly better lower bound on threshold as compared to any rigorously proven algorithmic bound [3, I]. The second moment method shows the existence of a satisfying assignment with uniform positive probability (w.u.p.p.). Thanks to the result of Friedgut for uniform model [ 1 0], existence of a satisfying assignment w.u.p.p. translates to existence of a satisfying assignment with high probability (w.h.p.). Thus, the second moment method gives a lower bound on the threshold. As there is no known Friedgut type result for regular random model, we assume that for regular random model existence of a satisfying assignments w.u.p.p. translates to existence of a satisfying assignments w.h.p. We derive the second moment of the number of satisfying assignments for regular random k-SAT for k >= 3. There are two aspects in deriving the lower bound using the second moment method. The first aspect is given any k, numerically evaluate the lower bound on the threshold. The second aspect is to derive the lower bound as a function of k for large enough k. We address the first aspect and evaluate the lower bound on threshold. The numerical evaluation suggests that as k increases the obtained lower bound on the satisfiability threshold of a regular random formula converges to the lower bound obtained for the uniform model. Similarly, we obtain lower bounds on the NAE-satisfiability threshold of the regular random formulas and observe that the obtained lower bound seems to converge to the corresponding lower bound for the uniform model as k increases.

Place, publisher, year, edition, pages
2010. Vol. 6175, 264-277 p.
Keyword [en]
Conjunctive normal forms, First moment methods, High probability, Lower bounds, Numerical evaluations, Positive probability, Random formulas, Random k-Sat, Random Model, Satisfiability, Satisfiability threshold, Satisfying assignments, Second moment methods, Second moments, Uniform model, Upper and lower bounds, Upper Bound, Boolean functions
National Category
Computer and Information Science Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-29227DOI: 10.1007/978-3-642-14186-7_22ISI: 000281446500022Scopus ID: 2-s2.0-77954986976OAI: oai:DiVA.org:kth-29227DiVA: diva2:392936
Note

QC 20110128

Available from: 2011-01-28 Created: 2011-01-27 Last updated: 2017-12-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Rasmussen, Lars KildehöjSkoglund, Mikael

Search in DiVA

By author/editor
Rathi, VishwambharAurell, ErikRasmussen, Lars KildehöjSkoglund, Mikael
By organisation
ACCESS Linnaeus CentreCommunication TheoryComputational Biology, CB
In the same journal
Lecture Notes in Computer Science
Computer and Information ScienceTelecommunications

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 63 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf