1
$\begingroup$

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?

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

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 \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)

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – baffld Mar 23 '14 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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