Proofs and certificates
Which statements have short proofs, and how do proof methods compare?
3 problemsProof complexity
The length and computational structure of mathematical proofs.
Also under Computational complexity
Collections
Browse collectionsA few problems to explore
2 totalNP versus coNP
Whenever yes answers have short efficiently checkable certificates, must no answers have them too?
Optimal propositional proof system
Can one efficiently checkable proof system match every other system’s proof lengths within a polynomial factor?