¿Quién introdujo la computación no determinista?

20

Tengo dos preguntas históricas:

¿Quién describió por primera vez el cálculo no determinista?

Sé que Cook describió problemas NP-completos, y que Edmonds propuso que los algoritmos P son algoritmos "eficientes" o "buenos".

Busqué en este artículo de Wikipedia y hojeé "Sobre la complejidad computacional de los algoritmos", pero no pude encontrar ninguna referencia a cuándo se discutió por primera vez la computación no determinista.

¿Cuál fue la primera referencia a la clase NP? ¿Era el artículo de Cook de 1971?

Philip White
fuente
55
NP también fue inventado más o menos simultáneamente por Levin al otro lado de la cortina de hierro. Además de Edmonds, Rabin y Cobham (cada uno por separado) también "introdujeron" P, aunque Edmonds fue quizás el más efectivo para justificar el punto de vista de P como "eficiente".
Joshua Grochow
El artículo de Karps 1972 se considera un contrapunto clave para el documento de Cook que muestra que hay muchos problemas NP completos; En cierto sentido, Cook solo demostró que el SAT estaba completo en NP y no era obvio después de ese documento cuán abarcador podría ser el concepto.
vzn
(breve reflexión adicional) por lo que los dos documentos Cook / Karp fueron como un "golpe 1-2" en la comunidad TCS / comprensión colectiva. Además, en preguntas históricas como esta, a veces los conceptos están "en el aire" en ese momento y no hay una única respuesta única / definitiva, sino algunas respuestas casi igualmente viables. otro lugar para buscar es el documento de Turings 1936 sobre TMs, nunca he visto a nadie analizar / deconstruir descartando de manera concluyente que nada en el largo documento se acerque al no determinismo.
vzn
otro ángulo más (sobre este tema complejo / multidimensional): el paralelismo tiene muchas similitudes con el no determinismo.
vzn
También es interesante notar que Godel reconoció la importancia de la complejidad y posiblemente previó P como los algoritmos "eficientes". rjlipton.wordpress.com/the-gdel-letter
evanb

Respuestas:

31

Siempre he visto la noción de no determinismo en la computación atribuida a Michael Rabin y Dana Scott. Definieron autómatas finitos no deterministas en su famoso documento Finite Automata and These Decision Problems , 1959. La cita del Premio Turing de Rabin también sugiere que Rabin y Scott introdujeron máquinas no deterministas.

Sasho Nikolov
fuente
11

Esto es lo que dice Odifreddi sobre el tema:

"Nuestro modelo de máquina de Turing es determinista, en el sentido de que las instrucciones deben ser consistentes (a lo sumo, una de ellas es aplicable en cualquier situación). Shannon [1948] introdujo elementos de aleatorización en dispositivos informáticos desde el principio. De Leeuw, Moore, Shannon y Shapiro [1956]. Existen básicamente dos modelos: las máquinas de Turing no deterministas se comportan, en una situación ambigua en la que podrían aplicarse instrucciones contradictorias, eligiendo uno de ellos al azar: su potencia de cálculo, al menos para 0, Las funciones de valor 1 (conjuntos) no exceden el poder de las deterministas. Las máquinas probabilísticas difieren de las no deterministas en que el siguiente estado tiene una probabilidad y, por lo tanto, las instrucciones en conflicto no tienen la misma posibilidad de ser elegidas por la máquina ".
[PAG. Odifreddi, Teoría de la recursión clásica, vol. 1, página 50]

Tenga en cuenta que la noción de no determinismo en el sentido de "existe + verificador" existía en la teoría de la computabilidad mucho antes de la teoría de la complejidad, por ejemplo , la forma normal de Kleene , la jerarquía aritmética . Otros modelos de computación como los sistemas post canónicos (conocidos al menos desde 1943) y las gramáticas tampoco son deterministas. Creo que incluso se puede llevar la noción a la época del cálculo epsilon de Hilbert y los operadores de elección.


Sobre NP, le pregunté a Steve Cook. Richard Karp introdujo el nombre NP para la clase de problemas computables de tiempo polinómico no determinista en su famoso artículo de 1972. Cook se refiere a la clase de problemas computables de la máquina de Turing no determinista del tiempo polinomial en su famoso artículo de 1971 que define las reducciones del tiempo polinomial y muestra que hay problemas completos, pero sin dar un nombre a la clase.

Antes de su trabajo, no había mucho interés en problemas computables en tiempo polinómico por máquinas de Turing no deterministas, solo después del trabajo de Karp quedó claro que hay tantos problemas naturales en NP. Después del artículo de Cook, algunas personas se interesaron, particularmente dos que se interesaron desde el principio (antes de que saliera el documento de Karp) fueron Michael Rabin y Allan Borodin .

El artículo de Karp de 1972 sorprendió a la gente al mostrar cuán generalizada es la completitud NP entre los problemas naturales.

Kaveh
fuente
Usar el término 'aleatorio' en este contexto es peligroso, no se refiere a la aleatoriedad en el sentido estadístico, solo al hecho de que una opción se deja en blanco.
reinierpost
@reinierpost, sí, es confuso que él diga que la máquina no determinista selecciona el siguiente estado al azar (pero en cualquier caso la máquina no determinista es confusa en sí misma, es por eso que las personas generalmente prefieren la definición de verificación de NP).
Kaveh
Nunca lo he encontrado confuso. Tal vez estoy tan completamente confundido que no me doy cuenta.
reinierpost
7

Rabin y Scott presentaron los autómatas finitos no deterministas con su trabajo de investigación publicado en la revista IBM, abril de 1959. En el trabajo mencionaron:

hemos adoptado una forma aún más simple de definición al eliminar una función de salida complicada y hacer que nuestras máquinas simplemente den respuestas "sí" o "no". Myhill también lo usó, pero nuestras generalizaciones a las máquinas "no deterministas", " bidireccionales" y "muchas cintas" parecen ser nuevas .

El documento completo se puede ver aquí: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf

usuario35319
fuente