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
Witness of unsatisfiability for a random 3-satisfiability formula
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
Show others and affiliations
2013 (English)In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 87, no 5, 052807- p.Article in journal (Refereed) Published
Abstract [en]

The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density alpha exceeds a critical value alpha(s) approximate to 4.267. Rigorously proving the unsatisfiability of a given large 3-SAT instance is, however, extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a reduction to 3-XORSAT, which permits the construction of a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses), is possible when the clause density alpha > 19. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when a scales at least linearly with the variable number N, but the focused local search algorithm works for clause density alpha > cN(b) with b approximate to 0.59 and prefactor c approximate to 8. The exponent b can be further decreased by enlarging the single parameter S of the focused local search algorithm.

Place, publisher, year, edition, pages
2013. Vol. 87, no 5, 052807- p.
National Category
Physical Sciences
Identifiers
URN: urn:nbn:se:kth:diva-124461DOI: 10.1103/PhysRevE.87.052807ISI: 000319254900009Scopus ID: 2-s2.0-84878475016OAI: oai:DiVA.org:kth-124461DiVA: diva2:636188
Note

QC 20130709

Available from: 2013-07-09 Created: 2013-07-05 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Aurell, Erik
By organisation
Computational Biology, CBACCESS Linnaeus Centre
In the same journal
Physical Review E. Statistical, Nonlinear, and Soft Matter Physics
Physical Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 49 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