Re:Why not string theory? Because enough is enough
by eru on Wednesday June 15, 2016 @11:49PM
(#11913820)
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.
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