Pseudopolynomiell

In der Komplexitätstheorie wird ein Algorithmus pseudopolynomiell genannt, wenn seine Laufzeit ein Polynom im numerischen Wert der Eingabe ist.

Beispiel

Wir betrachten das Problem des Primzahltests. Dass eine gegebene Zahl n eine Primzahl ist, lässt sich überprüfen, indem man explizit nachrechnet, dass sie sich durch keine der Zahlen $\{2,3,\dots ,n-1\}$ glatt teilen lässt. Dies benötigt n-2 Divisionen, wodurch die Laufzeit dieses naiven Algorithmus linear in n ist. Dennoch ist dies kein effizienter Algorithmus, wie man es von linearen Algorithmen normalerweise annimmt, weil z. B. bereits eine 9-stellige Eingabe Milliarden von Divisionen benötigt. Da in der Komplexitätstheorie die Komplexität eines Algorithmus basierend auf der Länge der Eingabe berechnet wird und die Länge (eine sinnvolle Kodierung vorausgesetzt) logarithmisch von n abhängt, fällt der geschilderte Algorithmus in die Klasse exponentieller Laufzeit.

Der Unterschied wird deutlich, wenn man dies mit einem echt polynomiellen Algorithmus vergleicht wie z. B. dem Algorithmus zur Addition von Zahlen: Das Addieren zweier 9-stelliger Zahlen benötigt etwa 9 Schritte, d. h., dieser Algorithmus ist wirklich polynomiell in der Länge der Eingabe.

Verallgemeinerung auf nichtnumerische Probleme

Obwohl der Begriff pseudopolynomiell fast ausschließlich für numerische Probleme verwendet wird, lässt sich das Prinzip verallgemeinern: Man nennt eine Funktion m pseudopolynomiell, wenn m(n) maximal eine polynomielle Abhängigkeit von der Problemgröße n und von einer zusätzlichen Eigenschaft k(n) der Eingabe hat. Numerische Probleme ergeben sich hieraus als Spezialfall, bei dem k der numerische Wert der Eingabe ist.

Die Unterscheidung zwischen dem Wert einer Zahl und ihrer Länge ist eine Frage der Kodierung: Würden numerische Eingaben unär kodiert, so würde pseudopolynomiell mit polynomiell zusammenfallen.

Literatur

• Michael R. Garey, David S. Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York NY u. a. 1979, ISBN 0-7167-1044-7.