Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems¶
Gomes, C. P., Selman, B., Crato, N., & Kautz, H. (2000). Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems. Journal of Automated Reasoning, 24(1), 1-2.
Cited by¶
1 citation across 1 artifact.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Backtracking
- Recognising the pattern enables reasoning about completeness-versus-speed trade-offs: a backtracking search is complete when the tree is finite and every branch is eventually tried, and relaxing completeness — through depth limits or randomised restarts — trades coverage for speed, the same trade that structures search in time-boxed negotiation and triaged debugging.
This sourceEstablishes randomized restarts as a way to trade completeness coverage for expected speed in backtracking search.
- Recognising the pattern enables reasoning about completeness-versus-speed trade-offs: a backtracking search is complete when the tree is finite and every branch is eventually tried, and relaxing completeness — through depth limits or randomised restarts — trades coverage for speed, the same trade that structures search in time-boxed negotiation and triaged debugging.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:af05d4721b03 · see in the full table