\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsthm}
\title{Universal Sequential Search Problems}
\author{L. A. Levin}
\date{}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\begin{document}
\maketitle
\begin{abstract}
The article examines several well-known 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.
\end{abstract}
\section{Introduction}
[Introduction remains the same as in the previous version]
\section{Definitions and Problems}
[Definitions and Problems section remains the same as in the previous version]
\section{Main Results}
Let $f(n)$ be a monotonic function.
\begin{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.
\end{theorem}
\begin{proof}
Let $P$ be a sequential search problem that cannot be solved in time less than $f(n)$ for argument length comparable to $n$. We will show that each of the problems 1-6 is at least as hard as $P$.
By Lemma 1 (proven below), problems 1-6 are universal sequential search problems. This means that $P$ can be reduced to each of these problems. Let's consider the reduction of $P$ to problem $i$ (where $i$ is any number from 1 to 6).
There exist three algorithms $r(x)$, $p(y)$, and $s(y)$, working in time comparable to the length of the argument, such that:
1) $P(x, p(y)) \Leftrightarrow$ Problem$_i(r(x), y)$
2) $P(x, y) \Leftrightarrow$ Problem$_i(r(x), s(y))$
Suppose, for contradiction, that problem $i$ can be solved in time less than $f(n)$. Then we could solve $P$ as follows:
1) Given input $x$ for $P$, compute $r(x)$.
2) Solve Problem$_i(r(x), y)$ in time less than $f(n)$.
3) If a solution $y$ is found, compute $p(y)$ to get a solution for $P$.
The total time for this procedure would be less than $f(n)$ (plus some time comparable to the input length for computing $r(x)$ and $p(y)$). This contradicts our assumption that $P$ cannot be solved in time less than $f(n)$.
Therefore, problem $i$ cannot be solved in time less than $f(n)$. Since $i$ was arbitrary, this applies to all problems 1-6.
\end{proof}
The idea of the proof is that problems 1-6 are ``universal sequential search problems''.
\begin{definition}
Let $A(x, y)$ and $B(x, y)$ define sequential search problems $A$ and $B$ respectively. We say that problem $A$ reduces to $B$ if there are three algorithms $r(x)$, $p(y)$, and $s(y)$, working in time comparable to the length of the argument, such that $A(x, p(y)) \Leftrightarrow B(r(x), y)$ and $A(x, y) \Leftrightarrow B(r(x), s(y))$ (i.e., from an $A$-problem $x$, it's easy to construct an equivalent $B$-problem $r(x)$). A problem to which any sequential search problem reduces is called ``universal''.
\end{definition}
Thus, the essence of the proof of Theorem 1 consists in the following lemma.
\begin{lemma}
Problems 1-6 are universal sequential search problems.
\end{lemma}
\begin{proof}[Proof Sketch]
We need to show that any sequential search problem can be reduced to each of the problems 1-6. We'll outline the reduction for Problem 2 (finding a DNF for a partial Boolean function).
Let $A(x, y)$ be any sequential search problem. We can encode the computation of $A(x, y)$ as a Boolean circuit. This circuit can be represented as a partial Boolean function $f_x$ where:
- The input represents $y$
- The output is 1 if and only if $A(x, y)$ is true
- The function is undefined for inputs that don't correspond to valid encodings of $y$
Now, finding a $y$ such that $A(x, y)$ is true is equivalent to finding a satisfying assignment for $f_x$, which in turn is equivalent to finding a DNF representation of $f_x$.
The reduction algorithms would work as follows:
- $r(x)$ constructs the partial Boolean function $f_x$
- $p(y)$ extracts $y$ from the satisfying assignment
- $s(y)$ encodes $y$ as an input to the Boolean function
Similar reductions can be constructed for the other problems, showing that each of them is universal.
\end{proof}
The described method apparently allows easy obtaining of results like Theorem 1 and Lemma 1 for most interesting sequential search problems. However, the problem remains to prove the condition present in this theorem. Numerous attempts have long been made in this direction, and a number of interesting results have been obtained (see, for example, [3, 4]). However, the universality of various sequential search problems can be established without solving this problem. In the system of Kolmogorov-Uspensky algorithms, the following can also be proved:
\begin{theorem}
For an arbitrary sequential search problem $A(x, y)$, there exists an algorithm that solves it in time optimal to within multiplication by a constant and addition of a value comparable to the length of $x$.
\end{theorem}
\begin{proof}[Proof Sketch]
The idea is to construct a "universal" algorithm that simulates all possible algorithms in parallel, allocating more and more time to each algorithm as the computation progresses.
Let $\{M_i\}$ be an enumeration of all algorithms (e.g., all Turing machines). We construct an algorithm $U$ that works as follows:
For $t = 1, 2, 3, ...$:
For $i = 1, 2, ..., t$:
Run $M_i$ on input $x$ for $2^{i-t}t$ steps
If $M_i$ outputs a $y$ such that $A(x, y)$ is true, return $y$
If there exists an algorithm that solves $A(x, y)$ in time $T(n)$, then $U$ will find a solution in time $O(T(n))$. The multiplicative constant comes from the overhead of simulating multiple machines, and the additive term comparable to the length of $x$ comes from the initial steps where $t$ is small.
This algorithm is optimal up to a constant factor because if there were a significantly faster algorithm, it would contradict the assumption that $T(n)$ was the time of the fastest algorithm.
\end{proof}
\section*{Acknowledgements}
The author expresses sincere gratitude to A. N. Kolmogorov, B. A. Trakhtenbrot, Ya. M. Barzdin, Yu. I. Albryton, and M. I. Degtyar for valuable discussion.
\begin{thebibliography}{4}
\bibitem{yablonsky} Yablonsky S. V. On algorithmic difficulties of synthesis of minimal contact circuits. Collection ``Problems of Cybernetics'', 2. Moscow, Fizmatgiz, 1959, 75-121.
\bibitem{zhuravlev} Zhuravlev Yu. I. Set-theoretic methods in Boolean algebra. Collection ``Problems of Cybernetics'', 8. Moscow, Fizmatgiz, 1962, 5-44.
\bibitem{trakhtenbrot} Trakhtenbrot B. A. Optimal computations and Yablonsky's frequency phenomenon. Seminar. Novosibirsk, ``Nauka'', Siberian Branch, 1965, 4, 5, 79-93.
\bibitem{degtyar} Degtyar M. I. On the impossibility of eliminating complete enumeration when calculating functions relative to their graphs. Reports of the USSR Academy of Sciences, 1969, 189, 4, 748-751.
\end{thebibliography}
\end{document}