<p>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:</p>

<p>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)) &lt; t(n)$.</p>

<p>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)} &lt; TIME(\tilde U)$. So we have $2^{TIME(B)} &lt; TIME(\{U(A_i)\})$.</p>

<p>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</p>

<p>$\forall c \; \exists A_i \;\; t(U, A_i) &gt; t(V, A_i) +c$</p>

<p>So $U$ cannot be efficient.</p>

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

CC BY-SA 3.0
2012-11-17T13:02:36.233Z
Great solution, thx!
Vanessa
CC BY-SA 3.0
2012-07-17T08:48:24.600Z
2012-07-18T09:16:08.203Z
2012-07-18T09:16:08.203Z
Ruhollah Majdoddin
<p>Levin's universal algorithm is an algorithm such that $t(U,A) &lt; s_V t(V,A) + t_V$. By modifying the algorithm (see for example Hutter's <a href="ftp://ftp.idsia.ch/pub/techrep/IDSIA-16-00.ps.gz">The Fastest and Shortest Algorithm for All Well-Defined Problems</a>), 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 <a href="http://eccc.hpi-web.de/report/2011/091/">this technical report</a>.</p>

<p>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).</p>

CC BY-SA 3.0
2012-07-01T19:09:36.537Z
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
Vanessa
CC BY-SA 3.0
2012-07-02T08:14:10.470Z
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?
Vanessa
CC BY-SA 3.0
2012-07-02T15:41:32.867Z
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$).
Yuval Filmus
CC BY-SA 3.0
2012-07-02T19:30:18.277Z
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
Vanessa
CC BY-SA 3.0
2012-07-01T17:22:45.907Z
2012-07-01T19:37:53.193Z
2012-07-01T19:37:53.193Z
Yuval Filmus
<p>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$</p>

<p>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)</p>

<p>I'm interested in exploring performance bounds on universal problem solvers</p>

<p>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$</p>

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

<p>$$t(U, A) &lt; t(V, A) + t_V $$</p>

<p>Here $t_V$ depends on $V$ but doesn't depend on $A$</p>

<blockquote>
  <p>Do efficient universal problem solvers exist?</p>
</blockquote>

<p>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</p>

<p>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)</p>

<p>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</p>

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

<cc.complexity-theory><ai.artificial-intel>
Efficient universal problem solver?
Vanessa
# Efficient universal problem solver?

(Asked by: username_0 on 2012-07-01)

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

**Tags:** cc.complexity-theory, ai.artificial-intel


---

## 2 answers

### Answer by username_1 on 2012-07-17. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Great solution, thx!  

---

### Answer by username_2 on 2012-07-01. Score: 12

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](ftp://ftp.idsia.ch/pub/techrep/IDSIA-16-00.ps.gz)), 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](http://eccc.hpi-web.de/report/2011/091/).

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).

> **Comments:**
> **username_0**: 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  
> **username_0**: 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?  
> **username_2**: 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$).  
> **username_0**: 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  

---

