Solucionador de problemas universal eficiente?

12

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 AA1nNnA

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

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 AUAt(U,A)UA

Um solucionador de problemas universal é chamado de "eficiente" quando, para qualquer solucionador de problemas universal V , temosUV

t(U,A)<t(V,A)+tV

Aqui depende de V , mas não depende de AtVVA

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

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 resultadoBAB

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

Vanessa
fonte

Respostas:

5

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 ) )gSSDTIME(t)SDTIME(t)tg(t(n))<t(n)

Ug(n)=22nASAiAi=A(i)U~(i)=U(Ai)AAiO(logi)BS22TIME(B)<TIME(U~)2TIME(B)<TIME({U(Ai)})

VAiB(i)A(i)B(i)

cAit(U,Ai)>t(V,Ai)+c

U

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

Ruhollah Majdoddin
fonte
Ótima solução, thx!
Vanessa
12

t(U,A)<sVt(V,A)+tVsV1

AsV

Yuval Filmus
fonte
1
U
1
sVV
sVtVV
1
Eu não entendo como Aliás se adicionou a condição V é comprovadamente um solucionador problema universal, que seria possível para eliminar a um termo dependente executando apenas algoritmos que podem ser provado ser agentes de resolução problema universal
Vanessa