NP versus coNP
Whenever yes answers have short efficiently checkable certificates, must no answers have them too?
Proofs and certificates
Which statements have short proofs, and how do proof methods compare?
Subjects: Proof complexity
Problems in this collection
3 problemsFrege proof lower bounds
Can one exhibit propositional truths whose proofs must be superpolynomially long even in a flexible standard deductive system?
Optimal propositional proof system
Can one efficiently checkable proof system match every other system’s proof lengths within a polynomial factor?