A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
The work
| Authors | B. A. Trakhtenbrot |
|---|---|
| Editors | |
| Type | article |
| Year | 1984 |
| Citekey | trakhtenbrot1984survey |
Where it appeared
| Published in | IEEE Annals of the History of Computing |
|---|---|
| Publisher | Institute of Electrical and Electronics Engineers |
| Volume | 6 |
| Issue | 4 |
| Pages | 384--400 |
Identifiers
| DOI | 10.1109/mahc.1984.10036 |
|---|---|
| OpenAlex | W2165813048 |
| ISSN | 1058-6180 |
Access
| Landing page | https://doi.org/10.1109/mahc.1984.10036 |
|---|
Empty on purpose
| copy |
Related
| Distinct from | cook1971complexity |
|---|
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
Abstract
Concerns about computational problems requiring brute-force or exhaustive search methods have gained particular attention in recent years because of the widespread research on the "P = NP?" question. The Russian word for "brute-force search" is "perebor. " It has been an active research area in the Soviet Union for several decades. Disputes about approaches to perebor had a certain influence on the development, and developers, of complexity theory in the Soviet Union. This paper is a personal account of some events, ideas, and academic controversies that surrounded this topic and to which the author was a witness and-to some extent-a participant. It covers a period that started in the 1950s and culminated with the discovery and investigation of non-deterministic polynomial (NP)-complete problems independently by S. Cook and R. Karp in the United States and L. Levin in the Soviet Union.
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-09-03 05:44 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Filed under
Cite it as
@article{trakhtenbrot1984survey,
title = {A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms},
author = {B. A. Trakhtenbrot},
year = {1984},
journal = {IEEE Annals of the History of Computing},
publisher = {Institute of Electrical and Electronics Engineers},
volume = {6},
number = {4},
pages = {384--400},
issn = {1058-6180},
doi = {10.1109/mahc.1984.10036},
}
This record lives at https://refs.drheap.org/trakhtenbrot1984survey/ and will keep doing so.