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 ...
more >>>