2 ms·
Thanks for this — I really appreciate how clearly you explained the issue. You're absolutely right that, by definition, a verifier for an NP language must retu
by vicentesteve 1y ago
Thanks for this — I really appreciate how clearly you explained the issue.
You're absolutely right that, by definition, a verifier for an NP language must return false for all certificates if the instance is not in the language. That’s a fundamental property, and I fully agree with it.
What I intended in my construction is that the verifier accepts only if the parity check specified by the certificate actually fails — it recomputes the encoded value
*_n(), verifies the parity check at index , and accepts only if there's a real mismatch. If the circuit is correct, then no matter what
or you give, that mismatch shouldn't appear, so the verifier should always reject.
That said, I totally see how the way it's currently written might be unclear or misleading. It’s very possible that I need to make this logic more explicit, or even re-express the verifier definition to better align with the formal NP structure. I’ll take a closer look and make sure that the construction is not only correct, but clearly communicates the intended behavior.
Thanks again for pointing this out in such a precise way — it's exactly the kind of critique that helps me make this better.
- immibis 1y agoAnother issue: In section 4.1 you seem to be assuming that not only is the halting problem solved, but that all Turing machines halt (and therefore there is an upper bound to how long all of them take to run).