ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > LENGTH OF PROOFS:
Reports tagged with Length of Proofs:
TR98-021 | 7th April 1998
Shai Ben-David, Anna Gringauze.

On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic.

Revisions: 1
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 >>>



ISSN 1433-8092 | Imprint