Hacker News new | past | comments | ask | show | jobs | submit login

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.



Absolutely, 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-kno...

https://blockgeeks.com/guides/what-is-zksnarks/


Unfortunately I found all of the story-like exposition infuriating: they never even say what the new conjectured lower bound is.


Likely 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?


100% 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.


Agreed! 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.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: