I am reading the wikipedia article on the definition of NP. The verifier based definition of the complexity class NP is given by:
Alternatively, NP can be defined using deterministic Turing machines as verifiers. 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$.
Elsewhere the definition is given as, language $L$ is in NP if there is a polynomial time Turing machine $M$ and polynomial $p$ such that all $x\in L$ satisfy
$$x\in\{0,1\}^*,\exists y: \space |x|\leq p(|y|),M(x,y)=1$$
The way I read the definition is that it gives two conditions of interest:
1) The solution given a certificate $y$ has to checkable in polynomial time.
2) The amount of certificates have to be bounded by polynomial.
The text then proceeds to an example of a problem in NP, the subset sum problem.
In order to explain the verifier-based definition of NP, consider the subset sum problem: Assume that we are given some integers, {−7,
−3, −2, 5, 8}, and we wish to know whether some of these integers sum
up to zero. Here, the answer is "yes", since the integers {−3, −2, 5}
corresponds to the sum (−3) + (−2) + 5 = 0. The task of deciding
whether such a subset with zero sum exists is called the subset sum
problem.To answer if some of the integers add to zero we can create an
algorithm which obtains all the possible subsets. As the number of
integers that we feed into the algorithm becomes larger, both the
number of subsets and the computation time grows exponentially.But notice that if we are given a particular subset we can efficiently
verify whether the subset sum is zero, by summing the integers of the
subset. If the sum is zero, that subset is a proof or witness for the
answer is "yes". An algorithm that verifies whether a given subset has
sum zero is a verifier. Clearly, summing the integers of a subset can
be done in polynomial time and the subset sum problem is therefore in
NP.
However, as I understand the text, it only shows that 1) applies. That is it is shown that given any subset of natural numbers it is checkable in polynomial time whether the natural numbers sum to a particular number. It is not shown that the length of the certificate is bounded by polynomial with respect to $x$.
Given that the certificates are all the subsets of the input set, and the amount of subsets of a set of size $n$ is $2^n$ which grows faster than polynomial, how are the certificates bounded by polynomial, and what is the purpose of the condition 2)? What about the graph isomorphism problem where the different bijections between two graphs grow at the rate $n!$ (in this case, it grows faster than any polynomial of $2^n$). When does condition 2) fail?
Best Answer
I may not be the best person to answer this as I only have a cursory background, but as I understand it, condition two states that the size of the certificate is bounded by a polynomial, not the number of them. For the example given above, the certificate might look like "$030215$" where the odd digits correspond to negative or positive if they are $0$ or $1$ respectively, and the even digits correspond to the numbers to be added. The Turing machine $M$ would then use this string, add the numbers together, and then spit out $1$ as $(-3)+(-2)+5=0$.
Another way you could feed these numbers in that only uses three digits could be $01110$. Here, a $1$ corresponds to the second, third, and fourth entry in the set and tells the machine to add these entries. Depending on the Turing machine $M$, this might be a better way to do it.
More generally, lets say our machine $M$ excepts binary as an input language, then using the second option we would need at most the number of elements of our set in order to express the certificate, which is definitely polynomial.