Qui a introduit le calcul non déterministe?

20

J'ai deux questions historiques:

Qui a décrit en premier le calcul non déterministe?

Je sais que Cook a décrit des problèmes NP-complets et qu'Edmonds a proposé que les algorithmes P soient des algorithmes "efficaces" ou "bons".

J'ai cherché dans cet article Wikipedia et j'ai survolé "Sur la complexité des algorithmes", mais je n'ai trouvé aucune référence à quand le calcul non déterministe a été discuté pour la première fois.

Quelle a été la première référence à la classe NP? Était-ce le papier de Cook de 1971?

reference-request soft-question ho.history-overview nondeterminism Philip White
la source
5
NP a également été inventé plus ou moins simultanément par Levin de l'autre côté du rideau de fer. En plus d'Edmonds, Rabin et Cobham (chacun séparément) ont également "introduit" P, bien qu'Edmonds soit peut-être le plus efficace pour justifier le point de vue de P comme "efficace".
Joshua Grochow
Le papier de Karps 1972 est considéré comme un contrepoint clé au papier de Cooks montrant qu'un tas de problèmes sont NP complets; dans un sens, Cook a seulement montré que le SAT était NP complet et il n'était pas évident après cet article à quel point le concept pouvait être englobant.
vzn
(brève réflexion), les deux articles Cook / Karp étaient comme un "coup de poing 1-2" sur la communauté / compréhension collective du TCS. aussi, sur des questions historiques comme celle-ci, parfois les concepts sont "dans l'air" à l'époque et il n'y a pas une seule réponse unique / définitive mais quelques réponses presque aussi viables. un autre endroit à regarder est l'article de Turings 1936 sur les MT, qui n'a jamais vu personne analyser / déconstruire de manière concluante que rien dans le long article ne se rapproche du non-déterminisme.
vzn
encore un autre angle (sur ce sujet complexe / multidimensionnel): le parallélisme a de nombreuses similitudes avec le non-déterminisme.
vzn
Il est également intéressant de noter que Godel a reconnu l'importance de la complexité et a peut-être prévu P comme algorithmes "efficaces". rjlipton.wordpress.com/the-gdel-letter
evanb

Réponses:

31

J'ai toujours vu la notion de non-déterminisme dans le calcul attribuée à Michael Rabin et Dana Scott. Ils ont défini les automates finis non déterministes dans leur célèbre article Finite Automata and Their Decision Problems , 1959. La citation de Rabin's Turing Award suggère également que Rabin et Scott ont introduit des machines non déterministes.

Sasho Nikolov
la source
11

Voici ce que dit Odifreddi sur la question:

"Notre modèle de machine de Turing est déterministe, en ce sens que les instructions doivent être cohérentes (tout au plus l'une d'elles est applicable dans une situation donnée). Les éléments de randomisation dans les dispositifs informatiques ont été introduits très tôt par Shannon [1948] et De Leeuw, Moore, Shannon et Shapiro [1956]. Il existe essentiellement deux modèles. Les machines de Turing non déterministes se comportent, dans une situation ambiguë où des instructions contradictoires pourraient être applicables, en choisissant au hasard l'une d'entre elles: leur puissance de calcul, au moins pour 0, Les fonctions à valeur 1 (ensembles) ne dépassent pas la puissance des fonctions déterministes. Les machines probabilistes diffèrent des fonctions non déterministes en ce que l'état suivant a une probabilité, et donc les instructions contradictoires n'ont pas la même chance d'être choisies par la machine. "
[P. Odifreddi, Théorie classique de la récursivité, vol. 1, page 50]

Notez que la notion de non-déterminisme au sens de "il existe + vérificateur" existait dans la théorie de la calculabilité bien avant la théorie de la complexité, par exemple la forme normale de Kleene , la hiérarchie arithmétique . D'autres modèles de calcul comme les systèmes post-canoniques (connus au moins depuis 1943) et les grammaires sont également non déterministes. Je pense que l'on peut même pousser la notion à l'époque du calcul epsilon de Hilbert et des opérateurs de choix.

À propos de NP, j'ai demandé à Steve Cook. Le nom NP pour la classe des problèmes calculables en temps polynomial non déterministes a été introduit par Richard Karp dans son célèbre article de 1972. Cook se réfère à la classe des problèmes calculables par machine de Turing non déterministe du temps polynomial dans son célèbre article de 1971 qui définit les réductions de temps polynomiales et montre qu'il y a des problèmes complets, mais sans donner un nom à la classe.

Avant son article, il n'y avait pas beaucoup d'intérêt pour les problèmes calculables en temps polynomial par les machines de Turing non déterministes, seulement après l'article de Karp, il est devenu clair que tant de problèmes naturels sont liés au NP. Après le document de Cook, certaines personnes se sont intéressées, en particulier deux qui se sont intéressées tôt (avant la publication du document de Karp): Michael Rabin et Allan Borodin .

L'article de Karp de 1972 a surpris les gens en montrant à quel point l'achèvement du NP est omniprésent parmi les problèmes naturels.

Kaveh
la source
Utiliser le terme «aléatoire» dans ce contexte est dangereux, il ne fait pas référence à l'aléatoire au sens statistique, juste au fait qu'un choix est laissé en blanc.
reinierpost
@reinierpost, oui, il est déroutant de dire que la machine non déterministe sélectionne le prochain état au hasard (mais en tout cas la machine non déterministe prête à confusion par elle-même, c'est pourquoi les gens préfèrent généralement la définition de vérification de NP).
Kaveh
Je n'ai jamais trouvé ça déroutant. Peut-être que je suis tellement confus que je ne le réalise pas.
reinierpost
7

Rabin et Scott ont présenté les automates finis non déterministes avec leur document de recherche publié dans le journal IBM, avril 1959. Dans le document, ils ont mentionné:

nous avons adopté une forme encore plus simple de la définition en supprimant une fonction de sortie compliquée et en demandant à nos machines de répondre simplement «oui» ou «non». Cela a également été utilisé par Myhill, mais nos généralisations aux machines «non déterministes», « bidirectionnelles» et «à bandes multiples» semblent être nouvelles .

Le document complet peut être consulté ici: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf

user35319
la source