Por tanto, está claro que las versiones no deterministas de los modelos computacionales, como la máquina de Turing, son equivalentes en "potencia" al modelo determinista.
Aparte de mostrar este hecho, ¿cuál sería el "propósito" de aprender el no determinismo?
Mi respuesta instictiva a esto es que la versión no determinista de una TM es más fácil de describir que la versión determinista.
¿Se le ocurren otras razones?
El no determinismo subyace a la importantísima cuestión P=NP.
La computación no determinista tiene una interpretación diferente. Consideremos, por ejemplo, la prueba de primalidad. No está claro cómo comprobar la primalidad (aunque ahora se conocen pruebas [probables] eficientes), pero sí está claro cómo convencerse de que un número es compuesto : todo lo que hay que hacer es encontrar una factorización no trivial. Esta es una propiedad que es fácil de verificar dado un testigo , en este caso la factorización no trivial. Por lo tanto, podemos construir un verificador no determinista muy sencillo para la composibilidad:
int verify_composite(int n, int a, int b) {
return (a > 1) && (b > 1) && (n == a* b);
}Este algoritmo es mucho más sencillo y rápido que los algoritmos conocidos que deciden la primalidad. Ahora, en principio, una TM podría recorrer todas las factorizaciones posibles; sin embargo, eso es bastante lento, y la gente conjetura que no se puede hacer de manera eficiente (aunque se puede hacer mejor que la búsqueda exhaustiva). Esto ilustra el poder del no-determinismo.
Hay muchos problemas combinatorios que son fáciles de comprobar dado un testigo, de forma unilateral. Un ejemplo es el problema del vendedor ambulante: ¿cuál es la ruta más eficiente que debe seguir un vendedor ambulante si desea visitar todas las ciudades importantes de Nueva York? Es fácil dar un testigo que demuestre que hay una ruta que tarda X días: basta con presentar la ruta. Sin embargo, no está tan claro que lo contrario sea posible; de hecho, la gente cree firmemente que es imposible dar un testimonio eficientemente verificable de que hay no ruta que tarda X días.
Los problemas que son eficientemente resolubles son capturados por la clase de complejidad P. Los problemas de decisión que son eficientemente verificables son capturados por NP. El problema de decidir si hay una ruta para el vendedor que tarda como máximo X días está, por tanto, en NP, pero el problema opuesto no se cree que se alinee en NP (y en particular, no en P).
Karp descubrió en los años 70 que muchos problemas combinatorios en NP se reducen unos a otros, en un sentido que implica que si uno de ellos está en P, entonces todos están en P. Cook fue capaz de demostrar que uno de estos problemas captura todo NP, en otras palabras, si ese problema particular está en P, que todo NP está en P; tales problemas se llaman NP-completos. Uno de los problemas estudiados por Karp fue el utilizado por Cook, por lo que todos los problemas que estudia son NP-completos. (De hecho, Karp fue precedido por Cook).
La gente cree firmemente que los problemas NP-completos no están en P; este es el conocido problema P=NP (la gente cree que las dos clases son diferentes). Por lo tanto, si su problema es NP-completo, usted sabe que es difícil de resolver en el peor de los casos . Aunque muchos de estos problemas tienden a ser solucionables (o al menos aproximadamente solucionables) en la práctica (es decir, en el caso medio).
Razón A: Para algunos otros modelos de computación útiles, el no determinismo marca la diferencia, por ejemplo los autómatas pushdown.
Razón B: El no determinismo cambia los resultados en tiempo de ejecución. En teoría, considere $P$ vs $NP$ En la práctica, consideremos el Quicksort (no) determinista.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
