# NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?

As a follow-up from my old question here, I'm wondering more about the equivalence proof. Intuitively, NP has been described as the class of all problems which a solution certificate can be verified in polynomial time. Let's say we have a problem $K$ in NP and we have a certificate $c_e$ obtained externally that proves a YES or NO result for $x$.

From my understanding of the proof implications, if we have a NTM which solves $K$ in polynomial time, this implies that there exists a verifier for $K$ which takes any certificate and says whether that specific certificate is a valid "solution" for if $x$ results in YES/NO. The proof involves the fact that the NTM generates its own certificate $c_n$ which the verifier then uses, but this has nothing to do with $c_e$ from what I see. From my understanding, the verifier should take any arbitrary certificate (including $c_e$) and verifies that it indeed leads to the answer. But instead, the verifier uses only the certificate $c_n$ created by the NTM to verify whether $x$ results in YES/NO. In other words, the verifier isn't able to check any arbitrary certificate - it's only able to check the one created by the NTM.

To rephrase in case I'm not making sense – constructing a verifier, in my interpretation, means this verifier can take any certificate and check whether it's a proof for $x$. But the equivalence proof has the verifier take a specific certificate $c_n$ created by the NTM and only checks whether that is a valid proof for $x$. So what makes the verifier able to verify for any arbitrary certificate $c_e$?

I must be getting confused somewhere. Is there any point which labels my misunderstanding? I'd really like to fully grasp the intuition of the proof.

• Thank you Yuval - I think I understand this part, but I'm not quite sure about an arbitrary certificate. If the machine receives a certificate, let's say $c_e$, how does the proof of equivalence demonstrate this exactly? That's more where I'm confused. – rb612 Jan 12 '18 at 5:23
• sorry, I should've been more clear with that. So going along with SAT, the verifier will take a boolean formula as input along with a certificate, which in this case would be a set of true/false values. Now there may be multple sets of true/false values that satisfy a boolean formula. So thus there's the possibility of multiple valid certificates for a satisfiable problem with a given input. Say that I come up with certificate $c_e$. I'm wondering how are we ensured that a verifier created from an NTM is able to verify my certificate? The NTM could possibly guess a different certificate. – rb612 Jan 12 '18 at 8:26