But it sounds like your wish is to keep your kid off screens in general, which I don't think age verification would accomplish.
Age verification actually gets almost no hate. Society-wide surveillance gets a lot; age verification just happens to be the "think of the children" excuse to shoe-horn in the society-wide surveillance. As OP described, if the age verification is implemented as a "zero-knowledge proof" then we have age verification without society-wide surveillance and nobody is complaining.
This coloring problem is NP complete and somehow the thing the prover is proving is encoded in the graph structure. At the end of the day, the only thing the verifier is sure of is that the prover can make the three colored graph, 1 bit that corresponds to the thing the verifier wants to know (eg - does the prover have a token that can show they are over 18).
There's a type of token called a JWT that's really common nowadays, which is composed of 3 parts: Metadata describing encryption for the third part, the actual base64-encoded data, and the encrypted signature. The second part would include "is over 18" and "expiration date" to limit reuse/abuse, and is trivially decoded by anyone to confirm there's no personal information in there.
You'd get this token from your government site and copy/paste it into the site needing verification. The government site would provide a standard public key that can be used with the third part of the JWT to confirm it hasn't been tampered with (verification is built-in to JWT libraries). There would only be one public key that rarely changes, allowing the site to cache it, preventing the government site from correlating users based on timestamps - they never see the JWT from the other site (verification is done locally), and the other site would only need to pull the public key once for however many thousands of people use it.
...that said technical issues aside, I kinda feel like this would be the most acceptable version simply because it doesn't require the average user to trust the math - they could go to a JWT-decoding website and look at it themselves.
I guess the practical answer is that it’s impossible because there’s always the option to have an adult perform the verification and then hand over the device to the minor
We already have penalties for adults mistreating children by exposing them to dangerous things, but this is orthogonal to age verification.
You meant logical criticism?
As a not super tech savvy parent I find it impossible to keep my son off screens. He always finds a workaround. So I'm a fan of age verification especially after reading The Anxious Generation, despite all the hate it gets from hacker news.