Solucionador de problemas universal eficiente?

Definir um "problema" para ser um algoritmo aceitar um número natural e retornando 0 ou 1, o qual devolve uma em pelo menos uma n ∈ N . Qualquer um desses n é chamado de "solução" para $A$$1$$n \in \mathbb{N}$$n$$A$

Definir um "solucionador de problemas universal" para ser um algoritmo aceitar um problema e retornar uma das suas soluções. Por exemplo, U pode funcionar repetindo todos os números naturais e executando sua entrada neles até 1 resultado (ele só precisa interromper a entrada válida)$U$$U$$1$

Estou interessado em explorar os limites de desempenho em solucionadores de problemas universais

Dado um solucionador universal problema e A um problema, denotam t ( U , A ) o tempo que leva U para a saída de produtos em cima de entrada aceitar $U$$A$$t(U, A)$$U$$A$

Um solucionador de problemas universal é chamado de "eficiente" quando, para qualquer solucionador de problemas universal V , temos$U$$V$

Aqui depende de V , mas não depende de $t_V$$V$$A$

Existem solucionadores de problemas universais eficientes?

Edição: Eu percebi que é possível alterar as definições de "problema" e "solucionador de problemas universal" em algo um pouco mais elegante e essencialmente equivalente. Um "problema" é um algoritmo sem entrada retornando 0 ou 1 (que para). Um "solucionador de problemas universal" é um algoritmo que aceita um problema e retorna seu resultado. É mais ou menos uma máquina universal de Turing

A definição antiga pode ser reduzida a uma nova definição, já que, dado que um problema no sentido antigo, podemos construir B um problema no novo sentido que apenas aplica o solucionador de problemas universal trivial do sentido antigo a A (o solucionador descrito no texto acima )$A$$B$$A$

A nova definição pode ser reduzida à antiga, já que, dado a um problema no novo sentido, podemos construir A um problema no sentido antigo que apenas calcula B e compara a entrada com o resultado$B$$A$$B$

O exemplo trivial de um solucionador de problemas universal de novo sentido é um algoritmo que simplesmente executa sua entrada

Não existe um solucionador de problemas universal eficiente. Intuitivamente, U deve ter o tempo de execução (quase) ideal para qualquer problema de decisão decidível; enquanto o teorema da aceleração diz que existem problemas de decisão decidíveis que não possuem um algoritmo ideal (nem mesmo em um sentido muito moderado). Para formalizar isso:

O teorema da aceleração do tempo (veja por exemplo [1])): Para todas as funções computáveis ​​(e super-lineares) existe um conjunto decidível S tal que, se S ∈ D T I M E ( t ), então S ∈ D T I M E ( t ′ ) para t ′ que satisfaz g ( t ′ ( n ) $g$$S$$S \in DTIME(t)$$S \in DTIME(t')$$t'$$g(t'(n)) < t(n)$

$U$$g(n)=2^{2n}$$A$$S$$A_i$$A_i = A(i)$$\tilde U(i)=U(A_i)$$A$$A_i$$O(\log i)$$B$$S$$2^{ 2 TIME(B)} < TIME(\tilde U)$$2^{TIME(B)} < TIME(\{U(A_i)\})$

$V$$A_i$$B(i)$$A(i)$$B(i)$

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

$U$

[1] Oded Goldreich, Complexidade Computacional, Uma Perspectiva Conceitual, teorema 4.8. O capítulo 4.2.1.2 também é relevante.

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

$A$$s_V$