1
$\begingroup$

One definition of the class NP is that there is a certificate whose size is bounded by a polynomial function of the problem instance size which can be used on a deterministic TM, along with the original input, to decide whether the input is a part of the language.

Doesn't this definition allow the trivial loophole where we let the certificate simply be 1 if the input is a part of the language and 0 otherwise? Then the deterministic just uses the certificate entirely and totally ignores the input.

$\endgroup$
2
$\begingroup$

The point that you're missing is that the deterministic algorithm is given an input to the NP problem and string and it has to say either "That string is a valid certificate for the input" or "That string is not a valid certificate for the input." For example, for compositeness, the verifier would have to be able to accept "Six is composite because it is two times three" and reject "Five is composite because it is two times three." This can be done easily, by checking the arithmetic and checking that the claim isn't something like "$p$ is prime because it is $p$ times one."

If the certificate is just one bit, the only way the verifier could check that a string is a valid certificate would be to ignore the certificate and solve the problem. Using compositeness again, the verifier's input would be just "Six is composite because, well, I promise it is" and "Five is composite because, well, I promise it is." The verifier can't just "believe" that the string is a valid certificate.

$\endgroup$

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.