Critical Behavior in the Satisfiability of Random Boolean Expressions
The work
| Authors | Scott Kirkpatrick; Bart Selman |
|---|---|
| Editors | |
| Type | article |
| Year | 1994 |
| Citekey | kirkpatrick1994critical |
Where it appeared
| Published in | Science |
|---|---|
| Publisher | American Association for the Advancement of Science (AAAS) |
| Volume | 264 |
| Issue | 5163 |
| Pages | 1297--1301 |
Identifiers
| DOI | 10.1126/science.264.5163.1297 |
|---|---|
| ISSN | 0036-8075 |
Access
| Landing page | https://doi.org/10.1126/science.264.5163.1297 |
|---|
From crossref.
Abstract
Determining the satisfiability of randomly generated Boolean expressions with k variables per clause is a popular test for the performance of search algorithms in artificial intelligence and computer science. It is known that for k = 2, formulas are almost always satisfiable when the ratio of clauses to variables is less than 1; for ratios larger than 1, the formulas are almost never satisfiable. Similar sharp threshold behavior is observed for higher values of k . Finite-size scaling, a method from statistical physics, can be used to characterize size-dependent effects near the threshold. A relationship can be drawn between thresholds and computational complexity.
How it got here
| How it got here | agent via crossref |
|---|---|
| Added | 2026-10-23 11:21 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Cite it as
@article{kirkpatrick1994critical,
title = {Critical Behavior in the Satisfiability of Random Boolean Expressions},
author = {Scott Kirkpatrick and Bart Selman},
year = {1994},
journal = {Science},
publisher = {American Association for the Advancement of Science (AAAS)},
volume = {264},
number = {5163},
pages = {1297--1301},
issn = {0036-8075},
doi = {10.1126/science.264.5163.1297},
}
This record lives at https://refs.drheap.org/kirkpatrick1994critical/ and will keep doing so.