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
Exhaustive enumeration unveils clustering and freezing in the random 3-satisfiability problem
SICS.
Université Paris-Sud, LPTMS, Université Paris-Sud.
2008 (English)In: Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, Vol. 78, no 4, 040101- p.Article in journal (Refereed) Published
Abstract [en]

We study geometrical properties of the complete set of solutions of the random 3-satisfiability problem. We show that even for moderate system sizes the number of clusters corresponds surprisingly well with the theoretic asymptotic prediction. We locate the freezing transition in the space of solutions, which has been conjectured to be relevant in explaining the onset of computational hardness in random constraint satisfaction problems.

Place, publisher, year, edition, pages
2008. Vol. 78, no 4, 040101- p.
Keyword [en]
Boolean functions, Freezing, Clustering, Complete sets, Computational hardnesses, Exhaustive enumerations, Freezing transitions, Geometrical properties, Number of clusters, Random constraint satisfaction problems, Satisfiability problems, System sizes
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-25885DOI: 10.1103/PhysRevE.78.040101ISI: 000260573800002OAI: oai:DiVA.org:kth-25885DiVA: diva2:360442
Note
QC 20101103. Uppdaterad från submitted till published (20101103). Tidigare titel: Exhaustive enumeration unveils clustering and freezing in random 3-SATAvailable from: 2010-11-03 Created: 2010-11-03 Last updated: 2010-11-03Bibliographically approved
In thesis
1. On state space structure and average case complexity in random K-SAT problems
Open this publication in new window or tab >>On state space structure and average case complexity in random K-SAT problems
2008 (English)Licentiate thesis, comprehensive summary (Other scientific)
Abstract [en]

This thesis gives an introduction to a currently active area in the cross-section between theoretical computer science and theoretical physics. In the last ten years it has been suggested that critical behaviour, usually seen in models from condensed matter physics, may be responsible for the intractability of NP complete computation problems. This would suggest a very deep connection between the two fields on the most fundamental level. How deep this connection really is is subject to ongoing research as well as the topic of this thesis. Some of the conjectrues from the physics community regarding computational hardness in certain problem classes has turned out to be wrong or misinterpreted but the gained interest in both fields has promising potiential in moving the research frontier forward.

The material presented in this thesis is the result of nearly two years work in trying to clearify how the results from physics can be interpreted in the language of actuall computation problems.

Abstract [sv]

Denna avhandling ger en introduktion till ett mycket aktivt forskningsområde i gränslandet mellan teortisk datalogi och teoretisk fysik. Under de senaste tio åren har det framkommit forskningsresultat som pekar på att kritiska fenomen, vanligen hemmahörande i modeller från teoretisk materialfysik, kan vara nyckeln till att förstå varför NP fullständiga problem är så svåra att lösa. Detta skulle innebära en mycket djup och fundamental koppling mellan de bägge områdena. Hur djup denna koppling verkligen är är temat i mycket av pågående forskning såväl som ämnet för denna avhandling. Vissa förutsägelser från den teoretiska fysiken har visat sig felaktiga eller feltolkade men det ökade intresset för dylika frågor inom bägge forskningområden ger hopp om att tillsammans kunna flytta from forskningsfronten.

Place, publisher, year, edition, pages
Stockholm: KTH, 2008. viii, 31 p.
Series
Trita-CSC-A, ISSN 1653-5723
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-4765 (URN)978-91-7178-971-6 (ISBN)
Presentation
2008-05-14, FR42, NORDITA, Roslagstullsbacken 23, 13:00
Opponent
Supervisors
Note
QC 20101103Available from: 2008-05-19 Created: 2008-05-19 Last updated: 2010-11-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Ardelius, John
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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