Betrachten wir die Definition noch einmal genauer. Ein Problem ist in \(NP\), wenn ein Verifikationsalgorithmus existiert, der \(L\) akzeptiert. Soweit so gut. Ein Verifikationsalgorithmus unterscheidet sich von einem „normalen“ Algorithmus dadurch, dass er neben der Instanz \(x\) des Problems, das er lösen soll, noch eine zusätzliche Eingabe \(y\) erhält. Dieses \(y\), das Zertifikat, soll ihm helfen, zu entscheiden, ob er \(x\) akzeptieren soll oder nicht. Betrachten wir z.B. das Erfüllbarkeitsproblem der Aussagenlogik. Die Eingabeinstanz ist eine Formel \(F\), das Zertifikat könnte dann eine (erfüllende) Belegung sein. Der Verifikationsalgorithmus überprüft dann lediglich, ob die Belegung tatsächlich eine erfüllende ist. Um \(NP\) zu erfassen darf man nun nicht einen uneingeschränkten Verifikationsalgorithmus nehmen, da man damit dann zu viel könnte. Der Verifikationsalgorithmus darf nur eine polynomielle Laufzeit haben. Ferner darf \(y\) nur polynomiell in der Länge von \(x\) sein. Z.B. könnte es sein, dass \(y\) nur maximal von der Länge \(|x|^2\) sein darf. Warum diese Einschränkung? Sonst wird das Zertifikat wieder zu mächtig und außerdem könnte man sonst eine deutlich längere Laufzeit im Vergleich mit \(x\) haben. Ist \(y\) nämlich deutlich länger als \(x\), also z.B. exponentiell in \(|x|\), dann arbeitet der Verifikationsalgorithmus zwar vielleicht polynomiell in der Länge von \(x\) und \(y\), was dann aber exponentiell in der Länge von \(x\) sein kann (da \(y\) ja so lang ist) und dies könnte der nichtdeterministische Algorithmus dann nicht mehr schaffen (siehe die nachfolgende Konstruktionsidee). Ist außerdem das Zertifikat länger als polynomiell in \(x\), so kann es von einer nichtdeterministischen, polynomialzeitbeschränkten Turingmaschine nicht geraten werden, da diese ja nur polynomiell viele Schritte in der Länge von \(x\) machen darf (siehe ebenfalls die nachfolgende Konstruktionsidee).