Quem introduziu a computação não determinística?

Eu tenho duas perguntas históricas:

Quem primeiro descreveu a computação não determinística?

Sei que Cook descreveu problemas de NP-completos e que Edmonds propôs que os algoritmos P são algoritmos "eficientes" ou "bons".

Pesquisei este artigo da Wikipedia e vasculhei "Sobre a complexidade computacional dos algoritmos", mas não consegui encontrar nenhuma referência sobre quando a computação não determinística foi discutida pela primeira vez.

Qual foi a primeira referência à classe NP? Foi o trabalho de Cook de 1971?

Eu sempre vi a noção de não determinismo em computação atribuída a Michael Rabin e Dana Scott. Eles definiram autômatos finitos não determinísticos em seu famoso artigo Finite Automata and Their Decision Problems , 1959. A citação do Rabin's Turing Award também sugere que Rabin e Scott introduziram máquinas não determinísticas.

Aqui está o que Odifreddi diz sobre o assunto:

"Nosso modelo de uma máquina de Turing é determinístico, no sentido de que as instruções são necessárias para serem consistentes (no máximo uma delas é aplicável em qualquer situação). Elementos aleatórios em dispositivos de computação foram introduzidos anteriormente por Shannon [1948] e De Leeuw, Moore, Shannon e Shapiro [1956]. Existem basicamente dois modelos: as máquinas de Turing não determinísticas se comportam, em uma situação ambígua em que instruções conflitantes podem ser aplicáveis, escolhendo aleatoriamente um deles: seu poder computacional, pelo menos para 0; As funções com valor 1 (conjuntos) não excedem o poder das determinísticas. As máquinas probabilísticas diferem das não determinísticas, pois o próximo estado tem uma probabilidade e, portanto, instruções conflitantes não têm a mesma chance de serem escolhidas pela máquina ".
[P. Odifreddi, Teoria Clássica da Recursão, vol. 1, página 50]

Note que a noção de não determinismo no sentido de "existe + verificador" existia na teoria da computabilidade muito antes da teoria da complexidade, por exemplo , a forma normal de Kleene , hierarquia aritmética . Outros modelos de computação, como os sistemas pós-canônicos (conhecidos pelo menos desde 1943) e gramáticas, também não são determinísticos. Acho que se pode até empurrar a noção para o tempo dos operadores de cálculo e escolha epsilon de Hilbert .

Sobre NP, perguntei a Steve Cook. O nome NP para a classe de problemas computáveis ​​não-determinísticos em tempo polinomial foi introduzido por Richard Karp em seu famoso artigo de 1972. Cook se refere à classe de problemas computáveis ​​não-determinísticos da máquina de Turing no tempo polinomial em seu famoso artigo de 1971, que define reduções no tempo polinomial e mostra que existem problemas completos, mas sem dar um nome à classe.

Antes de seu trabalho, não havia muito interesse em problemas computáveis ​​no tempo polinomial por máquinas de Turing não determinísticas, somente após o trabalho de Karp ficou claro que muitos problemas naturais estão em NP. Após o trabalho de Cook, algumas pessoas se interessaram, particularmente duas que se interessaram desde o início (antes da publicação do trabalho de Karp) foram Michael Rabin e Allan Borodin .

O artigo de Karp, de 1972, surpreendeu as pessoas ao mostrar como a abrangência generalizada da PN está entre os problemas naturais.

Rabin e Scott introduziram os autômatos finitos não determinísticos com seu trabalho de pesquisa publicado no jornal IBM, em abril de 1959. No artigo, eles mencionaram:

adotamos uma forma ainda mais simples da definição, eliminando uma função de saída complicada e fazendo com que nossas máquinas simplesmente dêem respostas "sim" ou "não". Isso também foi usado por Myhill, mas nossas generalizações para as máquinas "não determinísticas", " bidirecionais" e "muitas fitas" parecem novas .

Artigo completo pode ser visto aqui: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf