Umeå universitets logga

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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • 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
Revisiting the cavity-method threshold for random 3-SAT
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2019 (Engelska)Ingår i: Physical review. E, ISSN 2470-0045, E-ISSN 2470-0053, Vol. 99, nr 2, artikel-id 022106Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

A detailed Monte Carlo study of the satisfiability threshold for random 3-SAT has been undertaken. In combination with a monotonicity assumption we find that the threshold for random 3-SAT satisfies α3≤4.262. If the assumption is correct, this means that the actual threshold value for k=3 is lower than that given by the cavity method. In contrast the latter has recently been shown to give the correct value for large k. Our result thus indicate that there are distinct behaviors for k above and below some critical kc, and the cavity method may provide a correct mean-field picture for the range above kc.

Ort, förlag, år, upplaga, sidor
American Physical Society, 2019. Vol. 99, nr 2, artikel-id 022106
Nationell ämneskategori
Sannolikhetsteori och statistik
Identifikatorer
URN: urn:nbn:se:umu:diva-162509DOI: 10.1103/PhysRevE.99.022106ISI: 000458140700001PubMedID: 30934345Scopus ID: 2-s2.0-85061557736OAI: oai:DiVA.org:umu-162509DiVA, id: diva2:1344685
Tillgänglig från: 2019-08-21 Skapad: 2019-08-21 Senast uppdaterad: 2023-03-23Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextPubMedScopus

Person

Lundow, Per-HåkanMarkström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Lundow, Per-HåkanMarkström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Physical review. E
Sannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
pubmed
urn-nbn

Altmetricpoäng

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

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