Skip to main content
1 of 3
rb612
  • 499
  • 3
  • 13

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][1], 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.

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. [1]: How does (non)deterministic time relate to verifiability?

rb612
  • 499
  • 3
  • 13