Verifizierer

Einfache Sprache

Ein Verifizierer ist eine Algorithmus bei dem für alle Eingaben, die sich in der zu verifizierenden Sprach befinden, ein Wort (Zertifikat) existiert so, dass der Algorithmus $1$ ausgibt. Für andere Eingaben und beliebige Zertifikate gibt der Algorithmus $0$ aus.

Def. Verifizierer

Sei $S$ eine Sprache. Ein (derterministischer) Algorithmus $A$, der auf $\Sigma^*\times\Sigma^*$ arbeitet, heißt Verifizierer für $L$, wenn

$$L = \left\{x\in\Sigma^∗ |\exists c\in\Sigma^∗ \text{ mit } A(x, c) = 1\right\}\;.$$

Hierbei nennt man ein Wort $c$ mit $A(x,c)=1$ ein Zertifikat für $x$.