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
Polarised random κ-SAT
Lund University, Lund, Sweden.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2023 (Engelska)Ingår i: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 32, nr 6, s. 885-899Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

In this paper we study a variation of the random κ-SAT problem, called polarised random κ-SAT, which contains both the classical random κ-SAT model and the random version of monotone κ-SAT another well-known NP-complete version of SAT. In this model there is a polarisation parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random κ-SAT model, and at the other extreme we have the fully polarised model where p = 0, or 1. Here there are only two types of clauses: clauses where all κ variables occur pure, and clauses where all κ variables occur negated. That is, for p = 0, and p=1, we get an instance of random monotone κ-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarised random κ-SAT with p ≠ 1/2 is an upper bound on the threshold for random κ-SAT. Hence the satisfiability threshold for random monotone κ-SAT is at least as large as for random κ-SAT, and we conjecture that asymptotically, for a fixed κ, the two thresholds coincide.

Ort, förlag, år, upplaga, sidor
Cambridge University Press, 2023. Vol. 32, nr 6, s. 885-899
Nyckelord [en]
k-SAT, phase transition, random constraint satisfaction problem, satisfiability
Nationell ämneskategori
Datavetenskap (datalogi) Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-212544DOI: 10.1017/S0963548323000226ISI: 001033643900001Scopus ID: 2-s2.0-85165668678OAI: oai:DiVA.org:umu-212544DiVA, id: diva2:1786455
Tillgänglig från: 2023-08-09 Skapad: 2023-08-09 Senast uppdaterad: 2025-04-24Bibliografiskt granskad

Open Access i DiVA

fulltext(385 kB)64 nedladdningar
Filinformation
Filnamn FULLTEXT02.pdfFilstorlek 385 kBChecksumma SHA-512
02633f9a36348feec334d546c6d92ced25b6f367aea0123345fc1fcbfe3f367f1336c7495ad048351398d67f7a4b11d5db55cf19e85629e5887bf8a2730bf20c
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Markström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Markström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Combinatorics, probability & computing
Datavetenskap (datalogi)Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 110 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.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 393 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