Informaţiile care pot fi utilizate la verificarea optimalităţii într-un timp polinomial poartă numele de certificat de optimalitate. În mod similar, vom spune că informaţiile care pot fi folosite la verificarea admisibilităţii în timp polinomial se numesc certificat de admisibilitate. Pentru o problemă X=(D, F), pentru fiecare , vom nota cu Q_d un astfel de certifiat de admisibilitate. Dacă Q_d există, atunci el trebuie să fie scurt, în sensul că lungimea şirului binar dat prin el este o funcţie polinomială în lungimea intrărilor problemei.

Conceptul de algoritm nedeterminist pentru o problemă de admisibilitate pleacă de la imaginarea unui algoritm prin care se consideră alegeri aleatoare de şiruri binare în speranţa de a “ghici” Q_d. Un astfel de algoritm constă întotdeauna din două faze, una de ghicire şi una de verificare.

1. dacă , există un certificat de admisibilitate Q_d astfel încât, dacă se dă perechea (d, Q_d), atunci algoritmul răspunde afirmativ la apartenenţa lui d la F;
2. dacă , nu există ieşire şi astfel, când există ieşire,

Evaluarea unui algoritm nedeterminist se face doar relativ la etapa de verificare şi doar când în această etapă se dă un şi un certificat de admisibilitate.

urmator