Earlier this summer I attended a Celebration for Leonid Levin who recently turned 75. To prepare my talk I wanted to go back to Levin's 1971 two-page Russian masterpiece that covered both his independent discovery of NP-completeness and Universal Search. Boris Trakhtenbrot's wonderful Survey of Russian Approaches to Perebor has a messy translation of the Levin paper in the appendix. Could I use AI to get a cleaner version? TLDR Here's the PDF.
Let me first take a detour to when I was a graduate student in the 1980s. I went to meet my advisor Mike Sipser and found him with a couple of Russian students and postdocs carefully translating the latest paper from Alexander Razborov, then a young researcher at the Steklov Mathematical Institute in Moscow. Razborov had send a physical copy of his latest paper and they were translating word by word--would this be the paper that show NP sets don't have polynomial-size circuits and P ≠ NP? Spoiler alert: It wasn't, but the process remained etched in my memory four decades later.
But now we live in the 2020s and I turned to my friend Claude for help. I gave Claude the Russian PDF and asked Translate into English
Certainly, I'll translate the Russian text into English for you. Here's the translation:
PROBLEMS OF INFORMATION TRANSMISSION
Volume IX 1973 Issue 3
BRIEF COMMUNICATIONS
UDC 519.14
UNIVERSAL SEQUENTIAL SEARCH PROBLEMS
L. A. Levin
The article examines several well-known mass problems of the "sequential search type" and proves that these problems can only be solved in the time it takes to solve any problem of the specified type in general...
So far so good. Summarize the article.
This article by L. A. Levin, titled "Universal Sequential Search Problems," discusses a class of computational problems known as "sequential search problems" or "enumeration problems." Here's a summary of the key points:
1. The article addresses well-known computational problems that require exhaustive search (enumeration) to solve.
2. While many classical problems have been proven to be algorithmically unsolvable, there exists a class of problems that are solvable but require an impractically large amount of computation time.
3. These problems, called "sequential search problems," include tasks like minimizing Boolean functions, searching for proofs of limited length, and determining graph isomorphism.
4. While these problems can be solved by simple algorithms that enumerate all possibilities, such algorithms require exponential time, leading mathematicians to believe that simpler algorithms are impossible.
5. The article introduces the concept of "universal sequential search problems" - problems to which all other sequential search problems can be reduced.
6. Levin presents six specific problems (numbered 1-6 in the text) and claims they are universal sequential search problems.
7. The main theorem (Theorem 1) states that if there exists any sequential search problem that cannot be solved in less than f(n) time (for some function f), then the six presented problems also cannot be solved in less than f(n) time.
8. Another important result (Theorem 2) states that for any sequential search problem, there exists an algorithm that solves it in optimal time, up to a constant factor and an additive term comparable to the input length.
9. The article suggests that this approach can be extended to most interesting sequential search problems.
10. While the article doesn't solve the fundamental question of whether these problems truly require exponential time, it establishes relationships between different problems in this class.
This work is significant in computational complexity theory, as it relates various hard problems to each other and suggests a hierarchy of difficulty among computational tasks.
The summary is almost as long as the article.
Then I noticed the term "mass problems" that occurs throughout the paper. In the translation the word "mass" seems off. What are some alternatives?
You're right to notice that the word "mass" in this context might seem unusual or potentially confusing. In the original Russian text, the term used is likely "массовые задачи" (massovye zadachi), which is a term commonly used in Russian mathematical literature. However, in English, we typically use different terminology. Here are some alternative translations that might be more appropriate in this context:
1. "General problems" or "general computational problems"
2. "Large-scale problems"
3. "Broad classes of problems"
4. "Universal problems"
5. "Widely applicable problems"
6. "Common computational problems"
7. "Algorithmic problems"
8. "Computational class problems"
9. "Generic problems"
10. "Generalized problems"
In the context of this paper, the author is likely referring to problems that are not specific to a particular instance but represent a whole class or type of problem. The term "universal" is actually used later in the paper, which aligns well with this interpretation.
So, a more idiomatic translation might replace phrases like "classical mass problems" with "classical universal problems" or "broad classes of classical problems".
This choice of wording would better convey the idea that these are problems that apply broadly across many instances or types of computational tasks, rather than being specific to a particular case.
So "mass problems" is mass as in mass audience not mass as in physics. What if we left out the word "mass" completely.
You're right, omitting the word "mass" entirely could indeed improve the clarity and flow of the translation without losing the essential meaning. Let's consider how some key sentences would read without it:
1. Instead of:
"After clarifying the concept of an algorithm, the algorithmic unsolvability of a number of classical mass problems was proven..."
We could have:
"After clarifying the concept of an algorithm, the algorithmic unsolvability of a number of classical problems was proven..."
2. Instead of:
"However, if we assume that there exists some (even artificially constructed) mass problem of the sequential search type that cannot be solved by simple algorithms..."
We could have:
"However, if we assume that there exists some (even artificially constructed) problem of the sequential search type that cannot be solved by simple algorithms..."
3. And for the theorem:
"If there exists any problem of sequential search (quasi-sequential search) type that cannot be solved in time less than f(n) for argument length comparable to n, then problems 1-6 also have this property."
This approach works well because:
1. The context already implies that we're dealing with broad classes of problems, not specific instances.
2. The term "sequential search problems" itself conveys the idea of a general class of problems.
3. It makes the text more concise and easier to read in English.
4. It avoids potential confusion that might arise from an unusual use of the word "mass" in this context.
So yes, simply omitting "mass" throughout the translation would likely result in a clearer, more idiomatic English text while preserving the original meaning of the article.
Give me the full translation without the mass, which Claude dutifully did. Why stick with a text version. Format this nicely in latex.
Certainly! Here's the article formatted in LaTeX.
This LaTeX code will produce a nicely formatted version of the paper. It includes:
- Proper title, author, and abstract
- Sections for introduction, definitions and problems, and main results
- Theorem, lemma, and definition environments
- Proper mathematical formatting for equations and logical statements
- Enumerated list for the six problems
- Bibliography section
To compile this LaTeX document, you would need to save it as a .tex file and run it through a LaTeX compiler. The output will be a professionally formatted academic paper.
So I did and here is the final PDF.
Russian papers at the time famously had no proofs so for fun I tried Can you fill in the proofs of the theorems
Certainly! I'll expand the LaTeX document to include proofs for the theorems and lemma. Please note that since the original paper doesn't provide detailed proofs, I'll have to construct plausible proofs based on the information given and general knowledge of the field. These proofs should be considered as educated guesses rather than the actual proofs from Levin's original work.
Here's the updated LaTeX code with added proofs.
This expanded version includes proof sketches for Theorem 1, Lemma 1, and Theorem 2. These proofs are constructed based on the information given in the paper and general principles of computational complexity theory. They should give a good idea of the reasoning behind the theorems, but may not exactly match Levin's original proofs.
The main ideas in these proofs are:
- For Theorem 1: Using the universality of problems 1-6 to show that they must be at least as hard as any other sequential search problem.
- For Lemma 1: Demonstrating how an arbitrary sequential search problem can be reduced to one of the listed problems (in this case, Problem 2).
- For Theorem 2: Constructing a universal algorithm that simulates all possible algorithms in parallel, achieving optimal time complexity up to a constant factor.
These proofs maintain the paper's focus on the relationships between different types of sequential search problems and the idea of universal sequential search problems.
You can judge the proofs on your own.
