NP = { f: ?* ? ?* und f nichtdeterministisch  polynomial-zeitberechenbar } heißt die Klasse der npzb-Funktionen.

Definitionen:

Seien L, L‘ ? ?*

a) L‘ heißt polynomial reduzierbar auf L
dund wenn es existiert eine pzb-Funktion

f: ?* ? ?* mit: ? w ? ?* w ? L‘? f ( w ) ? L

b) L heißt NP-schwierig

dund wenn für jedes L‘? NP gilt: L‘ ist polynomial

reduzierbar auf L.

c) L heißt NP-vollständig
dund wenn L ? NP und L ist NP-schwierig.

Vorherige Folie

Nächste Folie

Zurück zur ersten Folie

Graphik-Version anzeigen