Skip to main content
added 8 characters in body
Source Link

It seems that the answerThere is negativeno 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.

It seems that the answer is negative. 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.

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.

Source Link

It seems that the answer is negative. 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.