enter image description here enter image description here enter image description here (Sipser's Chapter 7: Time COmplexity, Pgs 294-295)

If we have to prove the forward direction, then we must have the certificate along with the verifier. I don't get why we are "guessing the certificate"--essentially constructing the verifier-- if we already know one exists.

On the other hand, if you don't have the certificate, you can use a NTM to derive it and check w against c. So you don't need to pass any input into V. So V is useless.

I don't really understand this proof.

  • 1
    $\begingroup$ I don't understand your question. First, what is the theorem statement? You're asking us if a modified proof still works but what is it supposed to be proving. Second, NTMs don't derive things; they accept or reject strings. The quoted text in your title is usually taken as being the definition of NP, so there's nothing to prove. What definition of NP does Sipser use? $\endgroup$ Jul 26, 2019 at 15:15
  • $\begingroup$ @DavidRicherby Midway editing this question, I got the answer. The forward direction assumes the existence of a verifier...and it does have V and that V does have a certificate built into it...but we do not know what that c is ....and we need to know that c or otherwise we can't input anything into the verifier to verify as its inputs are of form <w,c>. So thats why we need to nondeterministically find c's and see which one is accepted by V. I think . $\endgroup$ Jul 26, 2019 at 15:28

1 Answer 1


By definition NP is the class of languages for which you can efficiently verify with a certificate that a string is in the language.

Informally; it is the class of problems that you can verify the solution to given a witness, but you cannot find one easily. If you could, then it would be in P.

A NTM can be seen as a unrealistic Turing machine which always guesses the right answer. Since the NTM is non-deterministic given an input x. We cannot be sure exactly what path he took to derive the solution, therefore a witness is needed.

For example;

Problem: Is 24 prime?

A NTM would guess the answer to be no and the certificate would be the number “4”.

A verifier presented with the certificate can divide 24 by 4 and also come to the conclusion that 24 is not prime.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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