The Library
Biased random k ‐SAT
Tools
Tools
Tools
Larsson, Joel and Markström, Klas (2021) Biased random k ‐SAT. Random Structures & Algorithms, 59 (2). pp. 238-266. doi:10.1002/rsa.20996 ISSN 1098-2418.
|
PDF
WRAP-Biased-random-k SAT-Larsson-2021.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (607Kb) | Preview |
Official URL: http://dx.doi.org/10.1002/rsa.20996
Abstract
The basic random k‐SAT problem is: given a set of n Boolean variables, and m clauses of size k picked uniformly at random from the set of all such clauses on our variables, is the conjunction of these clauses satisfiable? Here we consider a variation of this problem where there is a bias towards variables occurring positive—that is, variables occur negated w.p. 0 < p < 1 2 and positive otherwise—and study how the satisfiability threshold depends on p. For p < 1 2 this model breaks many of the symmetries of the original random k‐SAT problem, for example, the distribution of satisfying assignments in the Boolean cube is no longer uniform. For any fixed k, we find the asymptotics of the threshold as p approaches 0 or 1 2 . The former confirms earlier predictions based on numerical studies and heuristic methods from statistical physics.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QC Physics |
||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
| SWORD Depositor: | Library Publications Router | ||||||||
| Library of Congress Subject Headings (LCSH): | Combinatorial analysis , Phase transformations (Statistical physics) | ||||||||
| Journal or Publication Title: | Random Structures & Algorithms | ||||||||
| Publisher: | John Wiley & Sons, Inc. | ||||||||
| ISSN: | 1098-2418 | ||||||||
| Official Date: | 5 July 2021 | ||||||||
| Dates: |
|
||||||||
| Volume: | 59 | ||||||||
| Number: | 2 | ||||||||
| Page Range: | pp. 238-266 | ||||||||
| DOI: | 10.1002/rsa.20996 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||||
| Date of first compliant deposit: | 13 July 2021 | ||||||||
| Date of first compliant Open Access: | 14 July 2021 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
