Efficient universal problem solver? 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) &lt; 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
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 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).