Solucionador de problemas universal eficiente?

12

Definir un "problema" a ser un algoritmo aceptar un número natural y devolver 0 o 1 que devuelve 1 en al menos un n N . Cualquiera de tales n se llama una "solución" a AA1nNnA

Defina un "solucionador de problemas universal" como un algoritmo acepta un problema y devuelve una de sus soluciones. Por ejemplo, U puede funcionar haciendo un bucle sobre todos los números naturales y ejecutando su entrada en ellos hasta obtener 1 resultado (solo tiene que detenerse en una entrada válida)UU1

Estoy interesado en explorar los límites de rendimiento en solucionadores de problemas universales

Dado que un solucionador de problemas universal y A un problema, denote t ( U , A ) el tiempo que le lleva a U producir resultados al aceptar la entrada AUAt(U,A)UA

Un solucionador de problemas universal se llama "eficiente" cuando para cualquier solucionador de problemas universal V , tenemosUV

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

Aquí depende de V pero no depende de AtVVA

¿Existen solucionadores de problemas universales eficientes?

EDITAR: Me di cuenta de que es posible cambiar las definiciones de "problema" y "solucionador de problemas universal" en algo un poco más elegante y esencialmente equivalente. Un "problema" es un algoritmo sin entrada que devuelve 0 o 1 (que se detiene). Un "solucionador de problemas universal" es un algoritmo que acepta un problema y devuelve su resultado. Es más o menos una máquina universal de Turing

La vieja definición puede reducirse a una nueva definición, ya que dado un problema en el sentido antiguo, podemos construir B un problema en el nuevo sentido que solo aplica el solucionador de problemas universal trivial del viejo sentido a A (el solucionador descrito en el texto anterior )ABA

La nueva definición se puede reducir a la antigua, ya que dado un problema en el nuevo sentido, podemos construir A un problema en el antiguo sentido que solo calcula B y compara la entrada con el resultadoBAB

El ejemplo trivial de un solucionador de problemas universal de nuevo sentido es un algoritmo que simplemente ejecuta su entrada

Vanessa
fuente

Respuestas:

5

No existe un solucionador de problemas universal eficiente. Intuitivamente, U debería tener el tiempo de ejecución (casi) óptimo para cualquier problema de decisión decidible; mientras que el teorema de aceleración dice que hay problemas de decisión decidibles que no tienen un algoritmo óptimo (ni siquiera en un sentido muy leve). Para formalizar esto:

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, Complejidad computacional, una perspectiva conceptual, teorema 4.8. El Capítulo 4.2.1.2 también es relevante.

Ruhollah Majdoddin
fuente
Gran solución, gracias!
Vanessa
12

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

AsV

Yuval Filmus
fuente
1
U
1
sVV
sVtVV
1
No entiendo como. Por cierto, si agregué que la condición V es probablemente un solucionador de problemas universal, sería posible eliminar el término dependiente A ejecutando solo algoritmos que puedan ser probados para resolver problemas universales
Vanessa