3 ms·
Nope... it depends on the language you use to write the proof. Agda proofs for instance are in R.
by bodhiandpysics1 4y ago
Nope... 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.