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