uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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
Bounding the unsatisfiability threshold of random 3-SAT
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Mathematics.
2000 (English)In: RANDOM STRUCTURES & ALGORITHMS, ISSN 1042-9832, Vol. 17, no 2, 103-116 p.Article in journal (Refereed) Published
Abstract [en]

The satisfiability threshold conjecture states that fur a randomly generated formula of m clauses of exactly k literals over n variables, the probability that it is satisfiable, as n tends to infinity, changes abruptly from I to 0, as the ratio I = m/n is

Place, publisher, year, edition, pages
JOHN WILEY & SONS LTD , 2000. Vol. 17, no 2, 103-116 p.
Keyword [en]
unsatisfiability threshold; Rogers-Szego polynomials; Gaussian coefficients; generating functions; spin system; entropy; statistical physics; K-SAT
Identifiers
URN: urn:nbn:se:uu:diva-36599OAI: oai:DiVA.org:uu-36599DiVA: diva2:64498
Note
Addresses: Stamatiou YC, Univ Patras, Dept Comp Engn & Informat, Patras 26500, Greece. Univ Patras, Dept Comp Engn & Informat, Patras 26500, Greece. Comp Technol Inst, Patras 26321, Greece. Uppsala Univ, Dept Math, S-75106 Uppsala, Sweden. Carleton Univ,Available from: 2008-10-17 Created: 2008-10-17 Last updated: 2011-01-14

Open Access in DiVA

No full text

By organisation
Department of Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 488 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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