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

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • 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
Behavior of heuristics on large and hard satisfiability problems
KTH, Skolan för teknikvetenskap (SCI), Teoretisk fysik. (Theoretical Chemistry)
KTH, Skolan för teknikvetenskap (SCI), Teoretisk fysik. (Theoretical Chemistry)
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.

Ort, förlag, år, upplaga, sidor
2006. Vol. 74, nr 3, s. 037702-
Nyckelord [en]
Atomic physics, Benchmarking, Problem solving, Quantum theory, Random processes
Nationell ämneskategori
Fysik
Identifikatorer
URN: urn:nbn:se:kth:diva-8491DOI: 10.1103/PhysRevE.74.037702ISI: 000240870300105Scopus ID: 2-s2.0-33748771720OAI: oai:DiVA.org:kth-8491DiVA, id: diva2:13830
Anmärkning
QC 20100901Tillgänglig från: 2008-05-19 Skapad: 2008-05-19 Senast uppdaterad: 2017-12-14Bibliografiskt granskad
Ingår i avhandling
1. On state space structure and average case complexity in random K-SAT problems
Öppna denna publikation i ny flik eller fönster >>On state space structure and average case complexity in random K-SAT problems
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:nbn:se:kth:diva-4765 (URN)978-91-7178-971-6 (ISBN)
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

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Sök vidare i DiVA

Av författaren/redaktören
Ardelius, JohnAurell, Erik
Av organisationen
Teoretisk fysik
I samma tidskrift
Physical Review E. Statistical, Nonlinear, and Soft Matter Physics: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
Fysik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 214 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • 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