Cryptography Reference
In-Depth Information
2
n
2
n
im Allgemeinen
O
Tests durchgeführt
werden. Da die Tests polynomial sind, ist der naive Algorithmus
alles Durchpro-
bieren
somit exponentiell.
Übrigens gibt es durchaus Probleme mit exponentiellen Lösungs-Algorithmen,
die nicht in
NP
liegen.
(
)
Elemente. Es müssen also auch
O
(
)
Bemerkung
Der Begriff
mathematisches Problem
bleibt vage. Wie beim Begriff des
Algorithmus
und der
Komplexität
würde eine präzisere Fassung den Rahmen dieses Buches
sprengen. Anhand der Beispiele sollte aber ein Grundverständnis möglich sein.
Um diese Begriffe genauer fassen zu können, müssten wir den Begriff der
Turing-
Maschine
einführen und diskutieren. Das würde den Rahmen einer Einführung
in die algebraischen Methoden der Kryptologie verlassen. Daher verweisen wir
auf die Literatur.
Wie oben bereits festgehalten, liegt
P
in
NP
. Es ist eine offene Frage, ob die bei-
den Klassen evtl. gleich sind, ob es also zu jedem Problem aus
NP
einen polyno-
mialen Algorithmus zur Lösung gibt. Auf die Beantwortung dieser Frage ist ein
Preis von einer Million US-Dollar ausgesetzt. Es ist eines der
Millenium-Probleme
1
,
die vom privaten Clay Mathematics Institute zusammengestellt wurden.
4.1.7 Algorithmische Äquivalenz
≺
In der Klasse
NP
gibt es eine reflexive und transitive Relation
. Man schreibt
≺
Π
2
,
Π
1
wenn es einen polynomialen Algorithmus gibt, mit demman das mathematische
Problem
Π
1
auf das Problem
Π
2
zurückführen
kann. Genauer: Besitzt man ein
Orakel
zur Lösung von
Π
1
in polynomialer Zeit lösen. Ein
Ora-
kel
ist dabei eine (fiktive) Maschine, die auf Anfrage eine Lösung eines gewissen
mathematischen Problems ausgibt. Bei uns ist das
Π
2
, so kann man
Π
2
. Die Befragung eines Ora-
kels wird bei der Ermittlung von Laufzeiten vernachlässigt.
Beispiel
Für die Probleme
prim
(
N
)
„
prüfe, ob eine gegebene natürliche Zahl N eine Primzahl
(
)
(
)
≺
(
)
ist
“ und
Fak
,da
man
prim
auf das Problemder Faktorisierung zurückführen kann. Dass das keine
gute Strategie ist, soll uns hier nicht stören.
N
„
faktorisiere die natürliche Zahl N
“ gilt
prim
N
Fak
N
Zwei mathematische Probleme
≺
Π
1
nennt
man
algorithmisch äquivalent
. Den Nachweis dafür, dass hierdurch auf
NP
eine
Äquivalenzrelation definiert wird, haben wir als Übungsaufgabe formuliert.
Π
1
und
Π
2
mit
Π
1
≺
Π
2
und
Π
2
1
http://www.claymath.org/millennium/P_vs_NP/
