12
$\begingroup$

Define a "problem" to be an algorithm $A$ accepting a natural number and returning 0 or 1 which returns $1$ on at least one $n \in \mathbb{N}$. Any such $n$ is called a "solution" to $A$

Define a "universal problem solver" to be an algorithm $U$ accepting a problem and returning one of its solutions. For example, $U$ can work by looping over all natural numbers and running its input on them until $1$ results (it only has to halt on valid input)

I'm interested in exploring performance bounds on universal problem solvers

Given $U$ a universal problem solver and $A$ a problem, denote $t(U, A)$ the time it takes $U$ to produce output upon accepting input $A$

A universal problem solver $U$ is called "efficient" when for any universal problem solver $V$, we have

$$t(U, A) < t(V, A) + t_V $$

Here $t_V$ depends on $V$ but doesn't depend on $A$

Do efficient universal problem solvers exist?

EDIT: I realized it is possible to change the definitions of "problem" and "universal problem solver" into something slightly more elegant and essentially equivalent. A "problem" is an algorithm without input returning 0 or 1 (which halts). A "universal problem solver" is an algorithm accepting a problem and returning its result. It's more or less a universal Turing machine

Old definition can be reduced to new definition, since given $A$ a problem in the old sense, we can construct $B$ a problem in the new sense which just applies the trivial old-sense universal problem solver to $A$ (the solver described in the text above)

New definition can be reduced to old definition, since given $B$ a problem in the new sense, we can construct $A$ a problem in the old sense which just computes $B$ and compares the input to the result

The trivial example of a new-sense universal problem solver is an algorithm which simply runs its input

$\endgroup$
5
$\begingroup$

There is no efficient universal problem solver. Intuitively, U should have the (almost) optimal runtime for any decidable decision problem; while the speedup theorem says that there are decidable decision problems that have no optimal algorithm (not even in a very mild sense). To formalize this:

The time speed-up theorem (see for example [1])): For every computable (and super-linear) function $g$ there exists a decidable set $S$ such that if $S \in DTIME(t)$ then $S \in DTIME(t')$ for $t'$ satisfying $g(t'(n)) < t(n)$.

In the following, we work with the second definition. Let $U$ be any universal problem solver. Let $g(n)=2^{2n}$ and $A$ be an algorithm that decides $S$. Let $A_i$ be the no input TMs s.t $A_i = A(i)$. There is a TM $\tilde U(i)=U(A_i)$ with about a logarithmic overload in runtime (The coding of $A$ and $A_i$ differ only $O(\log i)$). By the speed-up thoerem, there is a TM $B$ that decides $S$ and $2^{ 2 TIME(B)} < TIME(\tilde U)$. So we have $2^{TIME(B)} < TIME(\{U(A_i)\})$.

Let $V$ be a universal problem solver such that for input $A_i$, it simulates $B(i)$ with a logarithmic overload in time. (Obviously the runtime functions of both $A(i)$ and $B(i)$ is unbounded) So we have

$\forall c \; \exists A_i \;\; t(U, A_i) > t(V, A_i) +c$

So $U$ cannot be efficient.

[1] Oded Goldreich, Computational Complexity, A Conceptual Perspective, theorem 4.8. Chapter 4.2.1.2 is also relevant.

$\endgroup$
  • $\begingroup$ Great solution, thx! $\endgroup$ – Vanessa Nov 17 '12 at 13:02
12
$\begingroup$

Levin's universal algorithm is an algorithm such that $t(U,A) < s_V t(V,A) + t_V$. By modifying the algorithm (see for example Hutter's The Fastest and Shortest Algorithm for All Well-Defined Problems), you can make $s_V$ a universal constant, though definitely not $1$ as you require. For related work, consult work by Hirsch, Itsykson and their students, for example this technical report.

Edit: As Squark comments, the runtime of Levin's algorithm also depends on the runtime of $A$, since it has to verify its answers. To get a constant $s_V$, all you need to do is to set the speeds of the various algorithms in geometric progression (rather than arithmetical progression, like in Levin's original algorithm).

$\endgroup$
  • 1
    $\begingroup$ If I understand correctly, Levin's $U$ is something along the lines of "let's run all possible algorithms in parallel, and each time one of them produces an answer let's test it and halt if it's correct". Since V is one of algorithms U is running it will find the answer in the same time as V up to a slowdown related to the fraction of "CPU time" allocated to V's "thread". However, I think you're missing an additional A-dependent term: the time required for testing the answer. Hutter's algorithm relies on proof search which is not enough for me since I make no assumptions about provability $\endgroup$ – Vanessa Jul 1 '12 at 19:09
  • 1
    $\begingroup$ Yuval, I'm missing something. In what sense $s_V$ becomes constant? It still depends on $V$ since different algorithms run with different speed, whatever progression you use, right? $\endgroup$ – Vanessa Jul 2 '12 at 8:14
  • $\begingroup$ I believe that you can (uniformly) bound $s_V$ at the cost of making $t_V$ grow even more wildly (but still constant for any given $V$). $\endgroup$ – Yuval Filmus Jul 2 '12 at 15:41
  • 1
    $\begingroup$ I don't understand how. Btw if I added the condition V is provably a universal problem solver, it would be possible to eliminate the A dependent term by running only algorithms which can be proved to be universal problem solvers $\endgroup$ – Vanessa Jul 2 '12 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.