1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – rb612 Jan 12 '18 at 5:23
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 12 '18 at 8:09
  • $\begingroup$ 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. $\endgroup$ – rb612 Jan 12 '18 at 8:26
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 12 '18 at 8:28
  • $\begingroup$ 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. $\endgroup$ – rb612 Jan 12 '18 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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