No.
En primer lugar, algunos algoritmos son inherentemente exponenciales: un número exponencial de pasos realizados por un algoritmo de este tipo no puede reducirse a un número polinómico de pasos. Un ejemplo simple es una máquina de Turing que, dado un número entero [math] n [/ math] escrito en notación unaria, escribe [math] 2 ^ n [/ math] en notación unaria en su cinta. La secuencia de pasos necesarios para escribir este número es necesariamente exponencial en el tamaño de la entrada.
En segundo lugar, aunque no sabemos si [math] \ mathrm {P} = \ mathrm {NP} [/ math], sabemos que [math] \ mathrm {EXPTIME} \ neq \ mathrm {P} [/ math]. Por lo tanto, hay problemas de decisión en [math] \ mathrm {EXPTIME} [/ math] que ninguna máquina de Turing de tiempo polinómico puede resolver. Todos los problemas completos de [math] \ mathrm {EXPTIME} [/ math] tienen esta propiedad.
- ¿Cuál es la relación entre aprendizaje automático, procesamiento de imágenes y visión por computadora?
- ¿Cómo explicaría que los datos importan más que los algos?
- Si voy a tener una licenciatura en Ciencias de la Computación, ¿debo asistir a un campamento de entrenamiento?
- ¿Qué universidades aceptarán un puntaje de 310 en ciencias de la computación?
- ¿Qué significa RESTful y por qué es significativo?
