1984/10/01 by B. A. Trakhtenbrot · 2 citations
Computer Science · #Computability, Logic, AI Algorithms #Algorithms and Data Compression #semigroups and automata theory
paper · doi:10.1109/mahc.1984.10036
openalex publication_date 1984/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23
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.