# Is Wikipedia's formal definition of NP correct?

A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that

• For all x and y, the machine M runs in time p(|x|) on input (x,y)
• For all x in L, there exists a string y of length q(|x|) such that M(x,y) = 1
• For all x not in L and all strings y of length q(|x|), M(x,y) = 0

I'm not an expert in the field but the first bullet point leads me to think that M must run in time p(|x|) regardless of the size of y, which doesn't seem to be true, at least if M gets to read y completely. What if |y| > p(|x|)?

Is the first bullet point of the definition correct? Shouldn't it be

For all x and y, the machine M runs in time p(|x|+|y|) on input (x,y)

Can you point me to an authoritative source with the original definition of NP based on deterministic verifiers?

• I think that is the accepted standard. When the witness is too long, the TM just doesn't read/use it all. – Austin Buchanan Mar 23 '14 at 1:58
• A definition can be (un)useful or (in)consistent with other definitions, but it's never correct or wrong. – Raphael Mar 23 '14 at 13:12

Definition 7.18: A verifier for a language $$A$$ is an algorithm $$V$$, where $$A = \{ w \mid V \text{ accepts } \langle w, c \rangle \text{ for some string } c \}.$$ We measure the time of a verifier only in terms of the length of $$w$$, so a polynomial time verifier runs in polynomial time in the length of $$w$$. A language $$A$$ is polynomially verifiable if it has a polynomial time verifier. (Sipser, 293)
Translating the wiki definition into the above, $$A = L$$, $$V = M$$, $$w = x$$, and $$c = y$$. It seems that the first condition of the wiki definition is correct, and this may make more sense given the alternative definition of NP. A language $$L$$ is in NP if there exists a non-deterministic TM $$N$$ that decides $$L$$ in non-deterministic polynomial time $$NTIME(n^k)$$. Here, the running time of $$N$$ is measured in terms of its input size $$n = |w| = |x|$$.
However, I have not seen nor am I familiar with the second condition, but that seems to set some upper bound on the length of $$y$$ so that $$|y|$$ is a polynomial in $$|x|$$, which should answer your question about if $$|y| > p(|x|)$$. I figure the second condition is to protect against padding arguments. At any rate, if $$p(|x|) < q(|x|)$$, then $$p(|x|) < |y| < q(|x|)$$, so $$|y|$$ is still a polynomial in $$|x|$$.
• I also want to point out that the second condition in the wiki may not be necessary. If $M$ does not reject inputs $y$ where $|y| \geq$, say $2^{O(|x|)}$, then $M$ is not a polynomial time verifier of $L$. This is obvious when the language is non-trivial, like $L = \{ \langle G, k \rangle \mid G \text{ has a clique of size at least } k \}$. If $|y| > |\langle G, k \rangle|$, then $y$ is obviously not a solution, so any polynomial-time verifier $M$ must reject such instances. Someone please correct me if I am wrong. – baffld Mar 23 '14 at 1:58