Timeline for NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 12, 2018 at 8:59 | comment | added | rb612 | I think my confusion is stemming from the fact that yours talks about the NTM reading from a certificate passed to the verifier as auxiliary input and his answer talks about the NTM guessing just any valid certificate, not necessarily the one passed to the verifier. It seems like those two are fundamentally very different. Nevertheless, I appreciate your effort and I hope I can find some resource that clears up the confusion I'm having. | |
| Jan 12, 2018 at 8:49 | comment | added | Yuval Filmus | That answer is really the same as mine, only presented differently. With this in mind, you should be able to understand the other answer. I can't help you any further. | |
| Jan 12, 2018 at 8:46 | comment | added | rb612 | Would you mind explaining though where I'm misunderstanding? I've seen the same explanation used in other contexts, and the essence of this question was to clear up where I'm misunderstanding. | |
| Jan 12, 2018 at 8:44 | comment | added | Yuval Filmus | You're not understanding the other answer correctly. It's not helpful to you, so I suggest ignoring it. | |
| Jan 12, 2018 at 8:43 | comment | added | rb612 | So here's what I get from your answer, which makes sense. A verifier takes a certificate, which the NTM reads as input, and checks to see if it accepts or rejects. That makes total sense, because the NTM's accepting or rejecting depends on the certificate. But from the other answer, a verifier takes a certificate $c_e$ and the NTM guesses another certificate $c_d$ which may or may not be the same one that the verifier took as input. So even if $c_e$ is invalid, if the NTM can find a valid $c_d$, it will accept. It seems like the two explanations conflict. | |
| Jan 12, 2018 at 8:38 | comment | added | Yuval Filmus | I suggest forgetting about that answer and focusing on my answer. After you understand this answer, you will be able to understand that answer. Focus on the definitions. | |
| Jan 12, 2018 at 8:36 | comment | added | rb612 | I suppose I may be misunderstanding the backwards implication outlined here: cs.stackexchange.com/a/58155/51868 - what's primarily confusing me is the fact that the certificate provided as auxiliary input seems to be irrelevant to whether the verifier accepts or not. It will accept any certificate iff the NTM can find a valid certificate for input $x$. In other words, we have the verifier and NTM – verifier takes certificate and defers to the NTM without passing the certificate to it. If NTM finds a valid certificate, verifier accepts. Else, it rejects. | |
| Jan 12, 2018 at 8:32 | comment | added | Yuval Filmus | You don't construct an NTM. The NTM is fixed once and for all. A certificate is an auxiliary input to the machine. A certificate is valid for an input if the machine accepts. That's it. | |
| Jan 12, 2018 at 8:31 | comment | added | rb612 | 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:28 | comment | added | Yuval Filmus | 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:26 | comment | added | rb612 | 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:09 | comment | added | Yuval Filmus | 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 5:23 | comment | added | rb612 | 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 11, 2018 at 10:40 | history | answered | Yuval Filmus | CC BY-SA 3.0 |