Polarised random k-SAT
Danielsson, Joel LU
and Markström, Klas
(2022)
- Abstract
- In this paper we study a variation of the random k-SAT problem, called polarized random k-SAT. In this model there is a polarization 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 k-SAT model, and at the other extreme we have the fully polarized model where p=0, or 1. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated. That is, for p=0 we get an instance of random monotone k-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability... (More)
- In this paper we study a variation of the random k-SAT problem, called polarized random k-SAT. In this model there is a polarization 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 k-SAT model, and at the other extreme we have the fully polarized model where p=0, or 1. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated. That is, for p=0 we get an instance of random monotone k-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 polarized random k-SAT is an upper bound on the threshold for random k-SAT. In fact, we conjecture that asymptotically the two thresholds coincide. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/005a2242-d69d-486e-b6d3-99a2480af143
- author
- Danielsson, Joel
LU
and Markström, Klas
- organization
- publishing date
- 2022-04-13
- type
- Working paper/Preprint
- publication status
- published
- subject
- keywords
- k-CNF
- pages
- 21 pages
- publisher
- arXiv.org
- DOI
- 10.48550/arXiv.2204.06615
- language
- English
- LU publication?
- yes
- id
- 005a2242-d69d-486e-b6d3-99a2480af143
- date added to LUP
- 2023-03-02 14:36:14
- date last changed
- 2023-03-03 10:57:23
@misc{005a2242-d69d-486e-b6d3-99a2480af143,
abstract = {{In this paper we study a variation of the random k-SAT problem, called polarized random k-SAT. In this model there is a polarization 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 k-SAT model, and at the other extreme we have the fully polarized model where p=0, or 1. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated. That is, for p=0 we get an instance of random monotone k-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 polarized random k-SAT is an upper bound on the threshold for random k-SAT. In fact, we conjecture that asymptotically the two thresholds coincide.}},
author = {{Danielsson, Joel and Markström, Klas}},
keywords = {{k-CNF}},
language = {{eng}},
month = {{04}},
note = {{Preprint}},
publisher = {{arXiv.org}},
title = {{Polarised random k-SAT}},
url = {{http://dx.doi.org/10.48550/arXiv.2204.06615}},
doi = {{10.48550/arXiv.2204.06615}},
year = {{2022}},
}