Optimal proof systems imply complete sets for promise classes
Johannes Köbler, Jochen Messner and Jacobo Torán
Abstract:
A polynomial time computable function whose range is a set L is called a proof system for L. In this setting, an h-proof for x is just a string w with h(w)=x. Cook and Reckhow defined this concept, and in order to compare the relative strength of different proof systems for the set TAUT of tautologies in propositional logic, they considered the notion of p-simulation. Intuitively, a proof system h' p-simulates h if any h-proof w can be translated in polynomial time into an h'-proof w' for h(w). We also consider the related notion of simulation between proof systems where it is only required that for any h-proof w there exists an h'-proof w' whose size is polynomially bounded in the size of w.
A proof system is called (p-)optimal for a set L if it (p-)simulates every other proof system for L. The question whether p-optimal or optimal proof systems for TAUT exist is an important one in the field. In this paper we show a close connection between the existence of (p-)optimal proof systems and the existence of complete problems for certain promise complexity classes like UP, NP intersects SPARSE, RP or BPP. For this we introduce the notion of a test set for a promise class C and prove that C has a many-one complete set if and only if C has a test set T with a p-optimal proof system. If in addition the machines defining a promise class have a certain ability to guess proofs, then the existence of a p-optimal proof system for T can be replaced by the presumably weaker assumption that T has an optimal proof system.
Strengthening a result from Krajicek and Pudlák, we also give sufficient conditions for the existence of optimal and p-optimal proof systems. We present a uniform approach to investigate the relationship between the existence of complete sets for promise classes and the existence of (p-)optimal proof systems for certain languages. Central to our approach is the notion of a test set which can be used to verify that a given nondeterministic polynomial time machine obeys the promise on a given input.
Ps-File: Optimal proof systems imply complete sets for promise classes