Change search
ReferencesLink to record
Permanent link

Direct link
Clustering of solutions in hard satisfiability problems
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
KTH, School of Information and Communication Technology (ICT).
2007 (English)In: Journal of Statistical Mechanics: Theory and Experiment, ISSN 1742-5468, no 10, P10012- p.Article in journal (Refereed) Published
Abstract [en]

We study numerically the solution space structure of random 3-SAT problems close to the SAT/UNSAT transition. This is done by considering chains of satisfiability problems, where clauses are added sequentially to a problem instance. Using the overlap measure of similarity between different solutions found on the same problem instance, we examine geometrical changes as a function of α. In each chain, the overlap distribution is first smooth, but then develops a tiered structure, indicating that the solutions are found in well separated clusters. On chains of not too large instances, all remaining solutions are eventually observed to be found in only one small cluster before vanishing. This condensation transition point is estimated by finite size scaling to be αc = 4.26 with an apparent critical exponent of about 1.7. The average overlap value is also observed to increase with α up to the transition, indicating a reduction in solutions space size, in accordance with theoretical predictions. The solutions are generated by a local heuristic, ASAT, and compared to those found by the Survey Propagation algorithm up to αc.

Place, publisher, year, edition, pages
2007. no 10, P10012- p.
Keyword [en]
Energy landscapes (experiment), Finite-size scaling, Network dynamics, Networks, Random graphs
National Category
Bioinformatics and Systems Biology
URN: urn:nbn:se:kth:diva-8492DOI: 10.1088/1742-5468/2007/10/P10012ISI: 000250725400006ScopusID: 2-s2.0-35948985998OAI: diva2:13831
QC 20100903Available from: 2008-05-19 Created: 2008-05-19 Last updated: 2010-09-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.
Trita-CSC-A, ISSN 1653-5723
National Category
Computer Science
urn:nbn:se:kth:diva-4765 (URN)978-91-7178-971-6 (ISBN)
2008-05-14, FR42, NORDITA, Roslagstullsbacken 23, 13:00
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 textScopus

Search in DiVA

By author/editor
Ardelius, JohnAurell, ErikKrishnamurthy, Supriya
By organisation
Computational Biology, CBSchool of Information and Communication Technology (ICT)
Bioinformatics and Systems Biology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 64 hits
ReferencesLink to record
Permanent link

Direct link