Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR98-021 | 22nd April 1998 00:00

On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic. Revision of: TR98-021

RSS-Feed




Revision #1
Authors: Shai Ben-David, Anna Gringauze.
Accepted on: 22nd April 1998 00:00
Downloads: 1218
Keywords: 


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.


Paper:

TR98-021 | 7th April 1998 00:00

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





TR98-021
Authors: Shai Ben-David, Anna Gringauze.
Publication: 15th April 1998 03:00
Downloads: 1204
Keywords: 


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.



ISSN 1433-8092 | Imprint