Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On state space structure and average case complexity in random K-SAT problems
KTH, Skolan för datavetenskap och kommunikation (CSC), Beräkningsbiologi, CB.
2008 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Stockholm: KTH , 2008. , s. viii, 31
Serie
Trita-CSC-A, ISSN 1653-5723
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-4765ISBN: 978-91-7178-971-6 (tryckt)OAI: oai:DiVA.org:kth-4765DiVA, id: diva2:13835
Presentation
2008-05-14, FR42, NORDITA, Roslagstullsbacken 23, 13:00
Opponent
Handledare
Anmärkning
QC 20101103Tillgänglig från: 2008-05-19 Skapad: 2008-05-19 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
Delarbeten
1. Behavior of heuristics on large and hard satisfiability problems
Öppna denna publikation i ny flik eller fönster >>Behavior of heuristics on large and hard satisfiability problems
2006 (Engelska)Ingår i: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, ISSN 1063-651X, E-ISSN 1095-3787, Vol. 74, nr 3, s. 037702-Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

 We study the behavior of a heuristic for solving random satisfiability problems by stochastic local search near the satisfiability threshold. The heuristic for average satisfiability (ASAT), is similar to the Focused Metropolis Search heuristic, and shares the property of being focused, i.e., only variables in unsatisfied clauses are updated in each step. It is significantly simpler than the benchmark WALKSAT heuristic. We show that ASAT solves instances as large as N=10(6) in linear time, on average, up to a ratio of 4.21 clauses per variable in random three-satisfiability. For K higher than 3, ASAT appears to solve instances of K-satisfiability up to the Montanari-Ricci-Tersenghi-Parisi full replica symmetry breaking (FSRB) threshold denoted alpha(s)(K) in linear time.

Nyckelord
Atomic physics, Benchmarking, Problem solving, Quantum theory, Random processes
Nationell ämneskategori
Fysik
Identifikatorer
urn:nbn:se:kth:diva-8491 (URN)10.1103/PhysRevE.74.037702 (DOI)000240870300105 ()2-s2.0-33748771720 (Scopus ID)
Anmärkning
QC 20100901Tillgänglig från: 2008-05-19 Skapad: 2008-05-19 Senast uppdaterad: 2017-12-14Bibliografiskt granskad
2. Clustering of solutions in hard satisfiability problems
Öppna denna publikation i ny flik eller fönster >>Clustering of solutions in hard satisfiability problems
2007 (Engelska)Ingår i: Journal of Statistical Mechanics: Theory and Experiment, ISSN 1742-5468, nr 10, s. P10012-Artikel i tidskrift (Refereegranskat) 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.

Nyckelord
Energy landscapes (experiment), Finite-size scaling, Network dynamics, Networks, Random graphs
Nationell ämneskategori
Bioinformatik och systembiologi
Identifikatorer
urn:nbn:se:kth:diva-8492 (URN)10.1088/1742-5468/2007/10/P10012 (DOI)000250725400006 ()2-s2.0-35948985998 (Scopus ID)
Anmärkning
QC 20100903Tillgänglig från: 2008-05-19 Skapad: 2008-05-19 Senast uppdaterad: 2010-09-03Bibliografiskt granskad
3. Circumspect descent prevails in solving random constraint satisfaction problems
Öppna denna publikation i ny flik eller fönster >>Circumspect descent prevails in solving random constraint satisfaction problems
Visa övriga...
2008 (Engelska)Ingår i: Proceedings of the National Academy of Sciences of the United States of America, ISSN 0027-8424, E-ISSN 1091-6490, Vol. 105, nr 40, s. 15253-15257Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We study the performance of stochastic local search algorithms for random instances of the K-satisfiability (K-SAT) problem. We present a stochastic local search algorithm, ChainSAT, which moves in the energy landscape of a problem instance by never going upwards in energy. ChainSAT is a focused algorithm in the sense that it focuses on variables occurring in unsatisfied clauses. We show by extensive numerical investigations that ChainSAT and other focused algorithms solve large K-SAT instances almost surely in linear time, up to high clause-to-variable ratios a; for example, for K = 4 we observe linear-time performance well beyond the recently postulated clustering and condensation transitions in the solution space. The performance of ChainSAT is a surprise given that by design the algorithm gets trapped into the first local energy minimum it encounters, yet no such minima are encountered. We also study the geometry of the solution space as accessed by stochastic local search algorithms.

Nyckelord
geometry of solutions local search, performance, random K-SAT
Nationell ämneskategori
Annan biologi
Identifikatorer
urn:nbn:se:kth:diva-8493 (URN)10.1073/pnas.0712263105 (DOI)000260360500010 ()2-s2.0-55749098814 (Scopus ID)
Anmärkning
QC 20100903. Uppdaterad från Submitted till Published (20100903)Tillgänglig från: 2008-05-19 Skapad: 2008-05-19 Senast uppdaterad: 2017-12-14Bibliografiskt granskad
4. Temperature dependent sampling in hard satisfiability problems
Öppna denna publikation i ny flik eller fönster >>Temperature dependent sampling in hard satisfiability problems
2008 (Engelska)Artikel i tidskrift (Övrigt vetenskapligt) Submitted
Abstract [en]

The solution sets of constraint satisfaction problems (CSPs)have been conjectured to to split up into clusters (connectedcomponents) when they are close to critically constrained,and this has been assumed to be related to computationalhardness. Simple stochastic local search (SLS) heuristics hashowever shown to be very efficient for many of these problems,and it has been unclear if this is related to clustering.In this work an SLS is used to sample the space of solutionsand the results are compared to the actual solution space generatedwith a complete solver. We show that different heuristicsfind different types of clusters. An increased greedinessresults in a sampling more uniform over the set of clusters,rather than over the set of solutions and the fastest solver visitsthe smaller cluster much more frequently than its solutionsdensity would imply. We also show that the level of randomness(temperature) is related in a non-trivial way to the abilityto escape from local minimas. This approach confirms thatclusters are important in understanding computational hardnessand may begin to explain the efficiency of SLSs in fragmentedsolution spaces.

Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:kth:diva-8494 (URN)
Anmärkning
QS 20120314Tillgänglig från: 2008-05-19 Skapad: 2008-05-19 Senast uppdaterad: 2018-01-13Bibliografiskt granskad
5. Exhaustive enumeration unveils clustering and freezing in the random 3-satisfiability problem
Öppna denna publikation i ny flik eller fönster >>Exhaustive enumeration unveils clustering and freezing in the random 3-satisfiability problem
2008 (Engelska)Ingår i: Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, Vol. 78, nr 4, s. 040101-Artikel i tidskrift (Refereegranskat) 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.

Nyckelord
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
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:kth:diva-25885 (URN)10.1103/PhysRevE.78.040101 (DOI)000260573800002 ()
Anmärkning
QC 20101103. Uppdaterad från submitted till published (20101103). Tidigare titel: Exhaustive enumeration unveils clustering and freezing in random 3-SATTillgänglig från: 2010-11-03 Skapad: 2010-11-03 Senast uppdaterad: 2018-01-12Bibliografiskt granskad

Open Access i DiVA

fulltext(2201 kB)416 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 2201 kBChecksumma MD5
0a93a6f054a0c0c2efbd9e6a5f4eeeae38a3e24958c65bc1369d2004211adb6d7ca924f8
Typ fulltextMimetyp application/pdf

Sök vidare i DiVA

Av författaren/redaktören
Ardelius, John
Av organisationen
Beräkningsbiologi, CB
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 416 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 690 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf