Sumber utama untuk ekivalensi waktu polinomial non-deterministik dan verifikasi waktu polinomial deterministik

Siapa orang pertama yang menunjukkan bahwa suatu bahasa ada dalam NP jika suatu sertifikat untuk bahasa tersebut dapat diverifikasi dalam waktu polinomial? Apakah kita memiliki kertas yang secara formal membuktikan ini? Kapan komunitas TCS mulai de-menekankan non-determinisme demi verifikasi? Saya tidak bisa, untuk kehidupan saya, menemukan referensi yang bagus untuk ini di luar teks-teks seperti Papadimitriou dan Arora dan Barak.

[Komentar yang diperluas] Saya berpikir bahwa "akar verifikasi" sudah terkandung dalam makalah tonggak Karp "Reducibilitas Diantara Masalah Combinatorial" (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)}$

Ada karakterisasi alternatif NP dalam hal mesin Turing nondeterministic ... [definisi perhitungan mesin Turing nondeterministic] ...

dan

$L \in NP$$L$