Abstract:
We investigate sufficient conditions for the existence of optimal propositional proof systems. We concentrate on conditions of the form ${\CoNF} = {\NF}$. We introduce a purely combinatorial property of complexity classes - the notions of {\em slim} vs. {\em fat} classes. These notions partition the collection of all previously studied time-complexity classes into two complementary sets. We show that for every slim class an appropriate collapse entails the existence of an optimal propositional proof system. On the other hand, we introduce a notion of a {\pps} {\em relative to an oracle} and show that for every fat class there exists an oracle relative to which such an entailment fails. As the classes $\P$ (polynomial functions), $\E$ ($2^{O(n)}$ functions) and $\EE$ ($2^{O(2^n)}$ functions) are slim, this result includes all the previously known sufficiency conditions for the existence of optimal propositional proof systems. On the other hand, the classes $\: \N{EXP}$, $\: \QP$ (the class of quasi-polynomial functions) and $\EEE: $($2^{O(2^{2^n})}$ functions), as well as any other natural time-complexity class which is not covered by our sufficiency result, are fat classes. As the proofs of all the known sufficiency conditions for the existence of optimal propositional proof systems carry over to the corresponding oracle-relativized notions, our oracle result shows that no extension of our sufficiency condition to non-slim classes can be obtained by the type of reasoning used so far in proofs on these issues.

Abstract:
We investigate sufficient conditions for the existence of optimal propositional proof systems (PPS). We concentrate on conditions of the form CoNF = NF. We introduce a purely combinatorial property of complexity classes - the notions of {\em slim} vs. {\em fat} classes. These notions partition the collection of all previously studied time-complexity classes into two complementary sets. We show that for every slim class an appropriate collapse entails the existence of an optimal PPS, while for every fat class there exists an oracle relative to which such an entailment fails. As the classes P (polynomial functions), E ($2^{O(n)}$ functions) and EE ($2^{O(2^n)}$ functions) are slim, this result includes all the previously known sufficiency conditions for the existence of optimal PPS's. On the other hand, the classes NEXP, QP (the class of quasi-polynomial functions) and EEE ($2^{O(2^{2^n})}$ functions), as well as any other natural time-complexity class which is not covered by our sufficiency result, are fat classes. We introduce a notion of a PPS {\em relative to an oracle}, As the proofs of all the known sufficiency conditions for the existence of optimal PPS's carry over to the corresponding oracle-relativized notions, this result shows that no extension of our sufficiency condition to non-slim classes can be obtained by the type of reasoning used so far in proofs on these issues.