¿Es posible decidir si un algoritmo dado es asintóticamente óptimo?

¿Existe un algoritmo para el siguiente problema:

Dada una máquina de Turing que decide un lenguaje , ¿hay una máquina de Turing decide modo que ? $M_1$ $L$
$M_2$ $L$ $t_2(n) = o(t_1(n))$

Las funciones y son los tiempos de funcionamiento más desfavorables de las máquinas Turing y respectivamente. $t_1$ $t_2$ $M_1$ $M_2$

¿Qué pasa con la complejidad del espacio?

complexity-theory computability undecidability decision-problem StaticBug
fuente

La respuesta definitivamente no es. Se sabe que determinar el peor tiempo de ejecución de una TM es indecidible.

chazisop 01 de

Pregunta más general .

Raphael

Respuestas:

Aquí hay un argumento simple para mostrar que son indecidibles, es decir, no hay algoritmos para verificar si un algoritmo dado es óptimo con respecto a su tiempo de ejecución o uso de memoria.

Reducimos el problema de detención en la cinta en blanco a su problema sobre la optimización del tiempo de ejecución.

Sea una máquina de Turing dada. Sea N la siguiente máquina de Turing: $M$

: en la entrada 1. Ejecute en una cinta en blanco para (como máximo) pasos. 2. Si no se detiene en pasos, ejecute un bucle de tamaño , luego devuelva NO. 3. De lo contrario, devuelva SÍ. $N$ $n$
$M$ $n$
$M$ $n$ $2^n$

Hay dos casos:

Si no se detiene en la cinta en blanco, la máquina funcionará durante pasos en la entrada . Entonces su tiempo de ejecución es . En este caso, obviamente no es óptimo. $M$ $N$ $\Theta(2^n)$ $n$ $\Theta(2^n)$ $N$
Si detiene en una cinta en blanco, la máquina se ejecutará durante un número constante de pasos para todos los lo suficientemente grandes , por lo que el tiempo de ejecución es . En este caso, es obviamente óptimo. $M$ $N$ $n$ $O(1)$ $N$

En breve:

M halts on blank tape \Leftrightarrow N is optimial

$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$

$M$ $N$ $N$ $M$

Se puede usar un argumento similar para el espacio, es decir, también es indecidible verificar si una máquina de Turing dada es óptima con respecto al espacio que usa.

Incluso una afirmación más fuerte es verdadera: no podemos decidir si una función computable dada es un límite superior en la complejidad de tiempo de calcular una función computable dada. Del mismo modo para el espacio. Es decir, incluso la teoría básica de la complejidad no puede ser automatizada por algoritmos (lo que puede considerarse una buena noticia para los teóricos de la complejidad).

Kaveh
fuente

M_{1}

$M_1$

n

$n$

n \mapsto YES

$n \mapsto \textrm{YES}$

N

$N$

n_{0}

$n_0$

n

$n$

n_{0}

$n_0$

M

$M$

Ah, la pregunta cambió desde la última vez que la leí. No importa.

Raphael

@ PålGD, creo que OP lo usó como un ejemplo (basado en la pregunta original publicada en cstheory). Puedes consultar los comentarios bajo esa pregunta.

Kaveh

Como otros mencionaron, la respuesta es no.

Pero hay un interesante artículo escrito por Blum " Una teoría independiente de la máquina sobre la complejidad de las funciones recursivas ". Mostró que hay algunas funciones con la propiedad de que no importa qué tan rápido pueda ser un programa para calcular estas funciones, existe otro programa para calcularlas mucho más rápido .

Una propiedad muy bonita!

Reza
fuente

-3

¡Decir ah! Si la respuesta fuera sí, estaríamos viviendo en un mundo diferente.

$A_0$ $A$ $L$ $A_0$ $A$

Desafortunadamente, esto no es posible, y de hecho, personalmente creo que probar la optimización (no trivial) es el problema más interesante (y difícil) en informática. Hasta donde sé, me alegraría que me corrigieran, no existe ningún resultado de optimización para ningún problema polinómico (excepto los resultados triviales de optimización, por supuesto, de los algoritmos que toman un tiempo proporcional al tamaño de entrada).

t a la t
fuente

Ω (N)

$\Omega(N)$

Ω (n \log n)

$\Omega(n \log n)$

@vonbrand: eso es lo que quise decir con algoritmos que son proporcionales al tamaño de entrada.

t a t t

@ttothet Ok, me temo que será infructuoso, pero lo intentaré nuevamente. 1) No, para nada. Si guarda solo un paso en cada entrada, tiene un algoritmo mejor que antes, a pesar de que tiene el mismo tiempo de ejecución asintótico. 2) No, no lo hace. También puede significar "No sé, pero si es así, entonces X". Esto no es infrecuente (cf P? = NP). 3) Se afirmó que había no hay límites inferiores no triviales (en asintótica, supongo) en absoluto . Eso está mal. Haz tu tarea, por favor.

Raphael

@ MartinJonáš Me refiero a una máquina de Turing de 2 cintas. Kaveh tiene un punto, la prueba del teorema de la jerarquía del tiempo da problemas que se pueden resolver en el tiempo poligonal con una complejidad arbitrariamente alta, pero los ejemplos no son exactamente naturales y no se sienten muy explícitos. Además, no se conoce ninguna jerarquía para el tiempo probabilístico, por lo que realmente no tenemos nada.

Sasho Nikolov