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?
Respuestas:
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.
fuente
Esto es lo que dice Odifreddi sobre el tema:
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.
fuente
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:
El documento completo se puede ver aquí: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf
fuente