TR97-026 Authors: Jochen Me\3ner, Jacobo Toran

Publication: 20th June 1997 11:12

Downloads: 1026

Keywords:

A polynomial time computable function $h:\Sigma^*\to\Sigma^*$ whose range

is the set of tautologies in Propositional Logic (TAUT), is called

a proof system. Cook and Reckhow defined this concept

and in order to compare the relative strenth of different proof systems,

they considered the notion of p-simulation. Intuitively a proof system

$h$ p-simulates a second one $h'$ if there is a polynomial time computable

function $\gamma$ translating proofs in $h'$ into proofs in $h$.

A proof system is called optimal if it p-simulates every other proof system.

The question of whether p-optimal proof systems exist is an important one

in the field. Kraj\'{\i}\v{c}ek and Pudl\'ak have given a sufficient condition

for the existence of such optimal systems, showing that if the deterministic

and nondeterministic exponential time classes coincide, then

p-optimal proof systems exist. They also give a condition implying the

existence of optimal proof systems

(a related concept to the one of p-optimal systems) exist.

In this paper we improve this result giving a weaker sufficient condition

for this fact. We show that if a particular class of sets with low information

content in nondeterministic double exponential time is included in

the corresponding nondeterministic class, then p-optimal proof systems exist.

We also show some complexity theoretical consequences that follow from

the assumption of the existence of p-optimal systems. We prove that

if p-optimal systems exist the the class UP (an some other related complexity

classes) have many-one complete languages, and that many-one complete sets for

NP $\cap$ SPARSE follow from the existence of optimal proof systems.