3 ms·
Umm. All proofs are in NP, not sure how that is relavent.
by bawolff 4y ago
Umm. All proofs are in NP, not sure how that is relavent.
- bodhiandpysics1 4y agoNope... it depends on the language you use to write the proof. Agda proofs for instance are in R.
- bawolff 4y agoIs it really a proof (in the philosophical sense) if it cannot be verified in polynomial time?
- klyrs 4y agoComputing the n-th Ramsey number R(n,n) is doable in exponential time. You can easily brute-force R(4, 4); a perfectly credible proof that takes exponential time! A credible proof must be verifiable in demonstrably finite time -- not necessarily polynomial.
- bodhiandphysics 4y agoSure! Exponential time can be very small in practice. Agda proofs are proofs when the compiler stops churning.
- fspeech 4y agoHard to find =/= hard to verify. Indeed that is the point of NP (which stands for "nondeterministic polynomial" time): solutions must be easy to check.