Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Polarised random κ-SAT

Danielsson, Joel Larsson LU orcid and Markström, Klas (2023) In Combinatorics Probability and Computing 32(6). p.885-899
Abstract

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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
k-SAT, phase transition, random constraint satisfaction problem, satisfiability
in
Combinatorics Probability and Computing
volume
32
issue
6
pages
885 - 899
publisher
Cambridge University Press
external identifiers
  • scopus:85165668678
ISSN
0963-5483
DOI
10.1017/S0963548323000226
language
English
LU publication?
yes
id
14fea5b0-ca72-4707-809f-eee4e080c9bd
date added to LUP
2023-11-22 14:21:31
date last changed
2024-01-09 15:44:59
@article{14fea5b0-ca72-4707-809f-eee4e080c9bd,
  abstract     = {{<p>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.</p>}},
  author       = {{Danielsson, Joel Larsson and Markström, Klas}},
  issn         = {{0963-5483}},
  keywords     = {{k-SAT; phase transition; random constraint satisfaction problem; satisfiability}},
  language     = {{eng}},
  number       = {{6}},
  pages        = {{885--899}},
  publisher    = {{Cambridge University Press}},
  series       = {{Combinatorics Probability and Computing}},
  title        = {{Polarised random κ-SAT}},
  url          = {{http://dx.doi.org/10.1017/S0963548323000226}},
  doi          = {{10.1017/S0963548323000226}},
  volume       = {{32}},
  year         = {{2023}},
}