The Perebor Problem

Are there problems for which the best possible approach is to perform a brute-force search of every possible solution?

During the Soviet-era, the perebor problem addressed this question. There are connections here to the question that arose in Western computer science: P versus NP. That is, is the set of problems that are easy to verify the correctness of necessarily also easy to solve?

I’ve found and lost and found again the idea of perebor so many times that I wanted to take a moment to document it here. Most recently, I was revisiting a 1984 paper on the topic: A Survey of Russian Approaches to Perebor Algorithms.

The Golden Rule relates the perebor problem to Communist ideology: a desire to believe that some problems rightly require effort and that the search for shortcuts—also known as more efficient solutions, as were pursued in the west—was anti-Marxist.

Whether or not one decides to anthropomorphize complexity, it has long fascinated me that the “East” and “West” divisions of the 20th century carried over into the conceptualization of fundamental properties of computational complexity.

Other related ideas: Kolmogorov Complexity, Computational Irreducibility.