Primäre Quelle für die Äquivalenz von nicht deterministischer Polynomzeit und deterministischer Polynomzeitverifikation

Wer hat als erster gezeigt, dass eine Sprache in NP ist, wenn ein Zertifikat für die Sprache in polynomialer Zeit verifiziert werden kann? Haben wir ein Papier, das dies formal beweist? Wann begann die TCS-Community, Nichtdeterminismus zugunsten der Überprüfbarkeit zu de-betonen? Über Texte wie Papadimitriou und Arora und Barak hinaus kann ich für mein Leben keine gute Referenz dafür finden.

[Ein erweiterter Kommentar] Ich denke, dass die "Wurzeln der Verifikation" bereits in Karps Meilensteinpapier "Reduzierbarkeit bei kombinatorischen Problemen" (1972) enthalten sind:

$P^{(2)}$$\Sigma^* \times \Sigma^*$$L^{(2)} \in P^{(2)}$$p$$L$

$L = \{ x \mid$$y$$\langle x,y \rangle \in L^{(2)}$$\log(y) \leq p(\log(x)) \}$

$y$

$L$$L^{(2)}$$p$

$NP$$P^{(2)}$

Es gibt eine alternative Charakterisierung von NP in Bezug auf nicht deterministische Turingmaschinen ... [Definition der Berechnung einer nicht deterministischen Turingmaschine] ...

und

$L \in NP$$L$