|
P ist die Menge aller Probleme, die sich in
polynomialer Zeit auf einer Mehrband-Turing-Maschine
(ist den uns vertrauten Computern äquivalent)
lösen lassen.
| ||||||
NP ist die Menge aller Probleme, die sich in
polynomialer Zeit auf einer nicht-deterministischen
Turing-Maschine (beliebige viele Pfade lassen sich
parallel, jedoch ohne Kommunikation untereinander betrachten)
lösen lassen.
| ||||||
Bislang ist unbekannt, ob P = NP oder
| ||||||
Die NP-vollständigen Probleme
| ||||||
Diese Theorie wurde von S. A. Cook (1971) und R. Karp (1972)
entwickelt.
|
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999 |