Browse Prior Art Database

A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms

IP.com Disclosure Number: IPCOM000129459D
Original Publication Date: 1984-Oct-01
Included in the Prior Art Database: 2005-Oct-06
Document File: 26 page(s) / 92K

Publishing Venue

Software Patent Institute

Related People

B. A. Trakhtenbrot: AUTHOR [+2]

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 ";bruteforce 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 nondeterministic polynomial (NP)-complete problems independently by S. Cook and R. Karp in the United States and L. Levin in the Soviet Union.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 4% of the total text.

Page 1 of 26

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Copyright ©; 1984 by the American Federation of Information Processing Societies, Inc. Used with permission.

A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms

B. A. Trakhtenbrot

  (Image Omitted: © 1984 by the American Federation of Information Processing Societies, Inc. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the AFIPS copyright notice and the title of the publication and its date appear, and notice is given that the copying is by permission of the American Federation of Information Processing Societies, Inc. To copy otherwise, or to republish, requires specific permission. Author's Address: School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, 69 978 Tel Aviv, Israel. © 1984 AFIPS 0164-1239/84/040384-400

A Survey of Russian Approaches to Perebor (Brute-Force Search) Algorithms

B. A. Trakhtenbrot .00/00)

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 "bruteforce 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 nondeterministic polynomial (NP)-complete problems independently by S. Cook and R. Karp in the United States and L. Levin in the Soviet Union.

Categories and Subject Descriptors: 1.2.8 [Artificial Intelligence] -- graph and tree search strategies; K.2 [History of Computing] -- people, software General Terms: Algorithms, Theory, Verification Additional Key Words and Phrases: brute-force search algorithms, perebor

Introduction

A perebor algorithm, or perebor for short, is Russian for what is called in English a "brute-force" or "exhaustive" search method. Other combinations of words also occur in translations from Russian, such as "successive trials," "sequential searching," and "thorough searching." To keep the historical flavor, I prefer to preserve in this paper the original term perebor and use such expressions as "perebor problems" (problems that are solvable by perebor), "impossibility of eliminating perebor," etc.

Example. Consider SAT, the satisfiability problem for formulas of the propositional logic. (1) Existential version: Given an arbitrary formula A(X1, ..., Xn), determine whether there exists an n-tuple of truth values that satisfies A. (2) Constructive versio...