Wikipedia\'s formal definition of NP based on deterministic verifiers states: A

Question

Wikipedia's formal definition of NP based on deterministic verifiers states:

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?

Explanation / Answer

I am currently reading "Introduction to the Theory of Computation" by Sipser and think that it is a great introduction to complexity (as well as automata and computability). Here are his definitions of Verifier and NP:

Definition 7.18: A verifier for a language $A$ is an algorithm $V$, where $A = { w mid V ext{ accepts } langle w, c angle ext{ 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)

Definition 7.19: NP is the class of languages that have polynomial time verifiers. (Sipser, 294)

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|$.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.