Efficient universal problem solver?

Question

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

Answer 1

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.

Answer 2

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