6 ms·
Slightly off-topic, this article has one of the best expositions I've seen (the Arthur-Merlin stuff) of P, NP, NP-complete, witnesses, and the idea of "evidence
by jmmcd 7y ago
Slightly off-topic, this article has one of the best expositions I've seen (the Arthur-Merlin stuff) of P, NP, NP-complete, witnesses, and the idea of "evidence" for what complexity class the problem is in.
- mpoteat 7y agoUnfortunately I found all of the story-like exposition infuriating: they never even say what the new conjectured lower bound is.
- nine_k 7y agoLikely it's the lower bound (of something) that an important conjecture in the paper gives? That is, it's not some new kind of a lower bound, but a way to refer to it?
- evrydayhustling 7y ago100% this. One of the cleanest descriptions of key insights and broader scientific landscape ("glide path" from quasipolynomial to P) I have seen. Erica, if you are seeing this, nice work and I'll be watching for more.
- dbchiem 7y agoAbsolutely, I think the author did a magnificent job!. Reading the article, all the intricacies (P/NP, polynomial/exponential, blind test, graph coloring) are quite clear and easy to comprehend. Here are some gentle articles on the zero-knowledge in case anyone is curious: https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/ https://blog.cryptographyengineering.com/2014/11/27/zero-kno... https://blockgeeks.com/guides/what-is-zksnarks/ https://blockgeeks.com/guides/what-is-zksnarks/
- meuk 7y agoAgreed! I was already prepared to be annoyed by sketchy metaphors that didn't quite make sense, but this was delightful and very informative to read.