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 nicht-numerische 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 die Zahl der (binären) Ziffern 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

• M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.