4 ms·
Is it really a proof (in the philosophical sense) if it cannot be verified in polynomial time?
by bawolff 4y ago
Is 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.