Who was the first person to show that a language is in NP if a certificate for the language can be verified in polynomial time? Do we have a paper that formally proves this? When did the TCS community start de-emphasizing non-determinism in favor of verifiability? I cannot, for the life of me, find a good reference for this beyond texts like Papadimitriou and Arora and Barak.
$\begingroup$
$\endgroup$
asked Oct 19, 2017 at 14:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
[An extended comment] I think that the "roots of verification" are already contained in Karp's milestone paper "Reducibility Among Combinatorial Problems" (1972):
...
Let $P^{(2)}$ denote the class of subsets $\Sigma^* \times \Sigma^*$ which are recognizable in polynomial time. Given $L^{(2)} \in P^{(2)}$ and a polynomial $p$, we define $L$ as follows:$L = \{ x \mid $ there exists $y$ s.t. $\langle x,y \rangle \in L^{(2)}$ and $\log(y) \leq p(\log(x)) \}$
(however Karp doesn't call $y$ a "certificate")
... We refer to $L$ as the language derived from $L^{(2)}$ by $p$-bounded existential quantification.
Definition 4. $NP$ is the set of languages derived from elements of $P^{(2)}$ by polynomial-bounded existential quantification.
There is an alternative characterization of NP in terms of nondeterministic Turing machines ... [definition of computation of a nondeterministic Turing machine] ...
and
... Theorem 1: $L \in NP$ if and only if $L$ is accepted by a nondeterministic Turing machine which operates in polynomial time ...
answered Oct 20, 2017 at 15:00
-
$\begingroup$ That looks like it to me. I must not have looked closely at Karp's paper because I assumed if the equivalence were attributed to him it'd be talked about along with everything else he did in that paper. $\endgroup$ Commented Oct 22, 2017 at 15:20