Polynomieller Verifizierer

Polynomieller Verifizierer

Einfache Sprache

Funktioniert wie ein Verifizierer, bloß dass es für alle Eingaben in der Sprache ein Zertifikat gibt wodurch der Algorithmus in Polynomialzeit läuft.

Def.Polynomieller Verifizierer

Ein Algorithmus $A$ ist ein polynomieller Verifizierer für eine Sprache $L$, wenn eine Konstante $d$ existiert so, dass es für jedes $x\in L$ ein Zertifikat $c$ (siehe Verifizierer) gibt mit

$$T_{A(x,c)}=\mathcal O(|x|^d)\;.$$

Diese Aussagen sind äquivalent:

1. $L$ ist polynomieller verifizierbar.
2. Es existiert ein polynomieller Verifizierer für $L$.