Komplexitätsklassen P und NP

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]  [Nächstes Kapitel]

*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
P
(=
#
NP
.
 
*Die NP-vollständigen Probleme

*gehören zu NP,
 
*und falls eines von ihnen zu P gehören würde, dann gilt NP = P.
 

*Diese Theorie wurde von S. A. Cook (1971) und R. Karp (1972) entwickelt.
 

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]  [Nächstes Kapitel]
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999