Wer hat die nicht deterministische Berechnung eingeführt?

20

Ich habe zwei historische Fragen:

Wer hat das nicht deterministische Rechnen zuerst beschrieben?

Ich weiß, dass Cook NP-vollständige Probleme beschrieb und dass Edmonds vorschlug, dass P-Algorithmen "effiziente" oder "gute" Algorithmen sind.

Ich suchte in diesem Wikipedia-Artikel und überflog "Über die rechnerische Komplexität von Algorithmen", fand aber keinen Hinweis darauf, wann nicht deterministische Berechnungen zum ersten Mal diskutiert wurden.

Was war der erste Hinweis auf die Klasse NP? War es Cooks Zeitung von 1971?

reference-request soft-question ho.history-overview nondeterminism Philip White
quelle
5
NP wurde auch mehr oder weniger gleichzeitig von Levin auf der anderen Seite des Eisernen Vorhangs erfunden. Zusätzlich zu Edmonds "führten" Rabin und Cobham (jeweils getrennt) P ein, obwohl Edmonds den Standpunkt von P möglicherweise am effektivsten als "effizient" rechtfertigte.
Joshua Grochow
Das Karps-Papier von 1972 gilt als zentraler Kontrapunkt zum Cooks-Papier und zeigt, dass eine Reihe von Problemen NP-vollständig sind. In gewisser Hinsicht zeigte Cook nur, dass SAT NP-vollständig ist, und es war nach diesem Aufsatz nicht klar, wie umfassend das Konzept sein könnte.
VZN
(Weitere kurze Überlegungen) Also waren die beiden Papiere Cook / Karp wie ein "1: 2-Schlag" auf die TCS-Community / das kollektive Verständnis. Bei historischen Fragen wie diesen sind Konzepte manchmal "in der Luft" und es gibt nicht eine einzige eindeutige Antwort, sondern ein paar nahezu gleichwertige Antworten. Ein weiterer Blickfang ist das Turings 1936-Papier über TMs, bei dem noch nie jemand analysiert / dekonstruiert hat, um schlüssig auszuschließen, dass nichts in dem langen Papier dem Nichtdeterminismus nahekommt.
VZN
Noch ein anderer Aspekt (zu diesem komplexen / mehrdimensionalen Thema): Parallelität hat viele Ähnlichkeiten mit Nichtdeterminismus.
vzn
Es ist auch interessant festzustellen, dass Godel die Bedeutung der Komplexität erkannt und möglicherweise P als die "effizienten" Algorithmen vorausgesehen hat. rjlipton.wordpress.com/the-gdel-letter
evanb

Antworten:

31

Ich habe immer den Begriff des Nichtdeterminismus in der Berechnung gesehen, der Michael Rabin und Dana Scott zugeschrieben wird. Sie definierten nicht deterministische endliche Automaten in ihrer berühmten Arbeit " Finite Automaten und ihre Entscheidungsprobleme" von 1959. Rabins Turing Award-Zitat legt auch nahe, dass Rabin und Scott nicht deterministische Maschinen einführten.

Sasho Nikolov
quelle
11

Folgendes sagt Odifreddi zu diesem Thema:

"Unser Modell einer Turing - Maschine ist deterministisch in dem Sinne, dass die Anweisungen konsistent sein müssen (höchstens eine von ihnen ist in einer gegebenen Situation anwendbar). Randomisierende Elemente in Computergeräten wurden von Shannon [1948] und Robert De Leeuw, Moore, Shannon und Shapiro [1956]: Grundsätzlich gibt es zwei Modelle: Nichtdeterministische Turing-Maschinen verhalten sich in einer mehrdeutigen Situation, in der möglicherweise widersprüchliche Anweisungen anwendbar sind, indem sie eine zufällig auswählen: ihre Rechenleistung, zumindest für 0, 1-wertige Funktionen (Mengen) überschreiten nicht die Potenz deterministischer. Probabilistische Maschinen unterscheiden sich von nicht deterministischen dadurch, dass der nächste Zustand eine Wahrscheinlichkeit hat und daher widersprüchliche Anweisungen nicht die gleiche Chance haben, von der Maschine ausgewählt zu werden. "
[P. Odifreddi, Klassische Rekursionstheorie, Bd. 1, Seite 50]

Man beachte, dass der Begriff des Nichtdeterminismus im Sinne von "es gibt + Verifizierer" in der Berechenbarkeitstheorie lange vor der Komplexitätstheorie existierte, z. B. Kleenes Normalform , arithmetische Hierarchie . Andere Rechenmodelle wie postkanonische Systeme (mindestens seit 1943 bekannt) und Grammatiken sind ebenfalls nicht deterministisch. Ich denke, man kann den Begriff sogar auf die Zeit von Hilberts Epsilon-Berechnungs- und Auswahloperatoren übertragen.

Über NP fragte ich Steve Cook. Der Name NP für die Klasse der nichtdeterministischen, polynomiell berechenbaren Probleme wurde von Richard Karp in seiner berühmten Arbeit von 1972 eingeführt. Cook bezieht sich in seiner berühmten Arbeit von 1971 auf die Klasse der nichtdeterministischen polynomiellen Zeitberechnungsprobleme von Turingmaschinen, in der die Polynomzeitverkürzungen definiert werden und gezeigt wird, dass es vollständige Probleme gibt, ohne der Klasse einen Namen zu geben.

Vor seiner Arbeit gab es nicht viel Interesse an Problemen, die in der Polynomzeit mit nicht deterministischen Turing-Maschinen berechenbar waren. Erst nach Karps Arbeit wurde klar, dass so viele natürliche Probleme in NP vorliegen. Nach Cooks Artikel interessierten sich einige Leute, besonders zwei, die sich früh dafür interessierten (bevor Karps Artikel herauskam), waren Michael Rabin und Allan Borodin .

Karps Arbeit von 1972 überraschte die Menschen, indem sie zeigte, wie weit verbreitet die NP-Vollständigkeit unter den natürlichen Problemen ist.

Kaveh
quelle
Die Verwendung des Begriffs „zufällig“ ist in diesem Zusammenhang gefährlich. Sie bezieht sich nicht auf Zufälligkeit im statistischen Sinne, sondern nur auf die Tatsache, dass eine Auswahl leer gelassen wird.
Reinierpost
@reinierpost, yest, es ist verwirrend, dass er sagt, dass die nicht deterministische Maschine den nächsten Zustand zufällig auswählt (aber auf jeden Fall ist die nicht deterministische Maschine für sich verwirrend, deshalb bevorzugen die Leute normalerweise die Verifizierungsdefinition von NP).
Kaveh
Ich habe es nie verwirrend gefunden. Vielleicht bin ich so durcheinander, dass ich es nicht merke.
reinierpost
7

Rabin und Scott führten die nichtdeterministischen endlichen Automaten in ihre Forschungsarbeit ein, die im IBM-Journal vom April 1959 veröffentlicht wurde. In der Arbeit erwähnten sie:

Wir haben eine noch einfachere Form der Definition übernommen, indem wir auf eine komplizierte Ausgabefunktion verzichtet haben und unsere Maschinen einfach „Ja“ oder „Nein“ antworten lassen. Dies wurde auch von Myhill verwendet, aber unsere Verallgemeinerungen zu dem „nichtdeterministisch“ , „two-way“ und „viele-Band“ Maschinen zu sein scheinen neu .

Das vollständige Papier kann hier eingesehen werden: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf

user35319
quelle