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

A non-deterministic Turing machine has a special instruction that allows it to non-deterministically "guess" a bit. The list of bits guessed by the machine is sometimes called a certificate. You can imagine that the guessed bits are taken from an auxiliary tape, whose contents you can think of as a certificate.

Here is an example. Consider the problem SAT: the input is a formula, and wish to find out whether the formula is satisfiable. A non-deterministic Turing machine for this problem "guesses" an assignment, and then checks ("verifies") that it satisfies the given formula. Alternatively, the machine gets a certificate and verifies that it is a satisfying assignment for the input formula. This is exactly the same Turing machine, only the process of non-deterministic guessing is visualized as reading from an auxiliary input, which we think of as a certificate.

• 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. Jan 12, 2018 at 5:23
• I'm not sure what you mean by an arbitrary certificate. The certificate just specifies the guesses of the machine. There is no freedom beyond that. Jan 12, 2018 at 8:09
• 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. Jan 12, 2018 at 8:26
• There's nothing wrong with having more than one valid certificate. There isn't any canonical valid certificate - all valid certificates have the same status. Jan 12, 2018 at 8:28
• So let's say I have an invalid certificate I present to the verifier. By the equivalence proof, we construct an NTM. NTM comes up with a correct certificate. Verifier uses that correct certificate created by the NTM to verify the solution. So even though I presented an invalid certificate, if the NTM finds a valid certificate, the verifier will accept. But shouldn't the verifier reject my invalid certificate? In other words, I don't see my (potentially invalid) certificate being used anywhere in the equivalence proof. Jan 12, 2018 at 8:31