3 ms·
This isn't necessarily true. There may be proofs so complex, they could exceed the limit of human cognition.
by glimshe 8d ago
This isn't necessarily true. There may be proofs so complex, they could exceed the limit of human cognition.
- pfdietz 8d agoThere certainly are such proofs. Even for simple decidable theories we have very large lower bounds on decision complexity (like double exponential), which implies large lower bounds on the function from "length of theorem statement" to "length of shortest proof". For undecidable theories, there is no computable function bounding this blowup from theorem length to proof length (otherwise, the theory would be decidable.)