\ 2^(O(n^k)) beschränkt ist. Dabei ist k eine geeignete Konstante und O(n^k) eine Polynom, das sich asymptotisch wie das Monom n^k verhält.

Stell dir eine polynomielle Subroutine X vor, deren Ausgabe doppelt so lang ist wie die Eingabe. Nun berechne mal

X( X( ... X( Eingabe ) ... ) ).

Bei einer Verschachtelungstiefe von N ist das Resultat demnach um den
Faktor 2^N länger als die Eingabe. Damit ist selbst bei einer linear zeitbeschränkten Funktion X die Laufzeit dieser Rekursion exponentiell in der Eingabelänge. Ein wichtiges Beispiel für eine Funktion, deren Ausgabe doppelt so lang ist wie die Eingabe, ist die Funktion X(y)=y^2.

ein Zertifikat ist ein Bitvektor, z.B. 010101011000.
Die Anzahl der Bitvektoren der Länge a ist 2^a, da man für jede Position 2 Möglichkeiten hat (0 oder 1), also insgesamt 2*2*2...*2 (a-mal)=2^a Möglichkeiten.
Nun gut, hier muß die Länge nicht genau O(n^k) sein, sondern ist höchstens O(n^k). Das ändert aber nicht viel, denn es gibt
2+2^2+...+2^a=2^(a+1)-2 Bitvektoren der Länge kleinergleich a, da es 
2 Bitvektoren der Länge 1
2^2 Bitvektoren der Länge 2
..
2^a Bitvektoren der Länge a gibt.

Das heißt, wenn die Zertifikatlänge nicht größer als O(n^k) ist, kann es insgesamt nicht mehr als
2^(O(n^k)+1)-2=2^(O(n^k)) Zertifikate geben.