Pierwotne źródło równoważności niedeterministycznej weryfikacji wielomianu i deterministycznej weryfikacji czasu wielomianu

Kto jako pierwszy pokazał, że dany język jest w NP, jeśli certyfikat dla tego języka można zweryfikować w czasie wielomianowym? Czy mamy dokument, który formalnie to potwierdza? Kiedy społeczność TCS zaczęła kłaść nacisk na niedeterminizm na rzecz weryfikowalności? Nie mogę znaleźć dla tego dobrego odniesienia poza tekstami takimi jak Papadimitriou, Arora i Barak.

[Rozszerzony komentarz] Myślę, że „korzenie weryfikacji” są już zawarte w kamieniu milowym Karpa „Reducibility Among Combinatorial Problems” (1972):

$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)}$

Istnieje alternatywna charakterystyka NP pod względem niedeterministycznych maszyn Turinga ... [definicja obliczenia niedeterministycznych maszyn Turinga] ...

i

$L \in NP$$L$