| 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.
|
 Additional Information
|
Citation:
B.A. Trakhtenbrot,
"A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms,"
IEEE Annals of the History of Computing,
vol. 06,
no. 4,
pp. 384-400,
Oct-Dec,
1984
|
RSS Feed