Polarised random κ-SAT
(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)
- author
- Danielsson, Joel Larsson LU and Markström, Klas
- organization
- publishing date
- 2023
- 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}}, }