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

Nah, P vs NP is a bigger factor here.

Basically, checking a proof for correctness takes polynomial time in the size of the proof. (Dependending on how you formalize your proofs, that might even be linear.)

Coming up with a reasonable sized proof is much harder. But if we had P=NP, then checking and finding a proof would be about equally hard.

See eg http://www.scottaaronson.com/papers/philos.pdf




Applications are open for YC Winter 2022

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

Search: