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.


1 Answer 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] ...


... Theorem 1: $L \in NP$ if and only if $L$ is accepted by a nondeterministic Turing machine which operates in polynomial time ...

  • $\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$ Oct 22, 2017 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.