Comment by immibis | Hacker News Reader

Comment by immibis | Hacker News Reader

Proving that parsing the input takes time polynomial in the size of the input is a red flag to me. Normally this is so obvious it's not worth stating.

It's also wrong (I think). It says skipping over l bits is O(l) but an actual Turing machine would have to go to the first unskipped bit and mark it skipped, then go back to the counter at the beginning and decrement it, and so on, making it O(l^2).

This is irrelevant since it's more sensible to give the input in a Turing-machine-friendly format when feeding it to a Turing machine.

Bigger red flag: I don't understand why the verifier has to take s in the certificate and evaluate Hn*(s) when Hn*(s) is already given as input. Also r is unused except in an edge case where it also wouldn't be needed? So basically both parts of the certificate are redundant according to the algorithm description and you could run the deterministic verifier without a certificate, meaning the problem is in P if this verifier algorithm is correct.

Another gaping flaw is that the LTC verification (I don't really understand this so will assume it's correct) tests a random sample of q bits yet the machine is said to be deterministic. Deterministic machines don't randomly sample things and have probabilities of getting the right answer.

Also the diagonalization procedure, to find an input that each decider gets wrong, is to just loop over all possible inputs and feed them to the decider and see if it gets it wrong??? Maybe I skipped over the part where you proved that would actually happen, but otherwise it's nonsense to just assume it's impossible for the decider to get them all right.

Edit: that part was section 4.1. In section 4.1 aren't you assuming that not only has the halting problem been solved, but that all machines halt?

This comment isn't meant to be an exhaustive list.

Thank you very much for spending the time reading it — I really appreciate such a thoughtful and thorough comment.

You're right on a couple of things. For instance, I probably overstated the time for parsing in a way that makes it sound like it's part of the actual hardness, when really it was just something I wanted to make explicit to be precise. And the point about randomness in the LTC part is valid — the verifier itself is fully deterministic and uses a fixed check index r, but the LTC construction it relies on is based on randomness. I see now that this wasn’t clearly separated in how I wrote it.

About the certificate: I get why it might look redundant at first. The key idea is that the verifier doesn’t go looking for a parity check that fails — it just verifies the one that’s provided. So r isn’t there because the verifier couldn’t find a violation, but because it doesn’t try to; it just checks whether the one it's told about actually fails. That said, I completely agree it could be better explained.

The diagonalization part definitely needs more clarity too. You're right: just looping over inputs only works if you can guarantee that failure will eventually happen — and that’s supposed to come from the circuit-counting bound. I’ll go back and make that implication and its formal reasoning much more explicit.

As for the machines halting — that’s handled by padding every D_i so it always halts within a fixed polynomial time (as mentioned in Lemma 4.1), but again, I agree that’s not emphasized enough and should be stated more clearly.

Overall, your feedback is incredibly helpful — not just in pointing out specific issues, but also in showing me how things might come across to someone reading this fresh. I'm already working on revising the affected sections, and I’d honestly be glad to hear any further thoughts you (or others) might have. Thanks again!

> The key idea is that the verifier doesn’t go looking for a parity check that fails — it just verifies the one that’s provided. So r isn’t there because the verifier couldn’t find a violation, but because it doesn’t try to; it just checks whether the one it's told about actually fails.

Then you failed. When using the certificate and verifier definition of NP, if the correct answer to the problem instance is false, there must be no certificate that makes the verifier return true.

A nondeterministic Turing machine is one that can clone itself and take two different paths without taking extra time. The copies can also make copies so it can clone as many times as it needs to. Copies that return false delete themselves, and if ANY copy returns true the overall answer is true (and we can delete all the copies). Any problem that can be solved by one of these is in NP. That's the definition of NP.

Equivalently, if we already know which one is going to return true, each time the machine wants to clone itself, we can tell the machine which copy is going to return true, and then it either continues being itself or pretends to be the clone, whichever one we told it, without actually cloning. Then we can run this on a normal Turing machine that doesn't clone itself. Of course, if we tell it wrong, it will return false even though it could have returned true if we told it right. This leads to the certificate definition of NP. The data we tell the machine about "the right way to pretend to clone" is the certificate.

Both are equivalent ways to define which problems are NP. The cloning version is the actual definition, but the certificate version is often more convenient, because, ya know, actual computers don't clone themselves.

If the answer to the problem is false, in the cloning version, all copies of the machine return false. That means in the certificate version, which only runs one copy, it will return false no matter which copy we choose, i.e. no matter which certificate we give it. Even if we give the wrong certificate, it's not possible to get a certificate machine for an NP problem to return true when the correct answer is false.

Your verifier machine is claimed to be a certificate machine that solves your problem, but you also say it sometimes returns true when the correct answer is false, if you give the wrong certificate. So there's something wrong with the setup here. I think the verifier machine is just wrong as it doesn't do what it needs to do to prove what you think it's proving.

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.

Another 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).

Reply on news.ycombinator.com