Source primaire pour l'équivalence du temps polynomial non déterministe et de la vérification du temps polynomial déterministe

Qui a été la première personne à démontrer qu'une langue est en NP si un certificat pour la langue peut être vérifié en temps polynomial? Avons-nous un document qui le prouve formellement? Quand la communauté TCS a-t-elle commencé à mettre l'accent sur le non-déterminisme en faveur de la vérifiabilité? Je ne peux pas, pour la vie de moi, trouver une bonne référence pour cela au-delà de textes comme Papadimitriou et Arora et Barak.

reference-request Logan Mayfield
la source

Réponses:

[Un commentaire étendu] Je pense que les "racines de la vérification" sont déjà contenues dans le document de référence de Karp "Réductibilité parmi les problèmes combinatoires" (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)}$

Il existe une caractérisation alternative de NP en termes de machines de Turing non déterministes ... [définition du calcul d'une machine de Turing non déterministe] ...

$L \in NP$ $L$

Marzio De Biasi
la source

Cela me ressemble. Je ne dois pas avoir regardé de près le document de Karp parce que je supposais que si l'équivalence lui était attribuée, il en serait question avec tout ce qu'il faisait dans ce document.

Logan Mayfield