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?