NP versus coNP
Whenever yes answers have short efficiently checkable certificates, must no answers have them too?
Proof complexity
Within Proof complexity · Search all subjects
Optimal propositional proof system
Can one efficiently checkable proof system match every other system’s proof lengths within a polynomial factor?