Revision #1 Authors: Shai Ben-David, Anna Gringauze.

Accepted on: 22nd April 1998 00:00

Downloads: 2628

Keywords:

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.

TR98-021 Authors: Shai Ben-David, Anna Gringauze.

Publication: 15th April 1998 03:00

Downloads: 2670

Keywords:

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.