Complete problems for promise classes by optimal proof systems for test sets
Johannes Köbler, Jochen Meßner · 2002
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. Basically, we show that a promise class C has a many-one complete language if and only if there is a test set for C which has a p-optimal proof system. As an application we are able to improve earlier results. For example, we show that NP/spl cap/co-NP has a many-one complete language, provided that the set TAUT of all valid boolean formulas as well as the set SAT of all satisfiable boolean formulas have p-optimal proof systems. We also apply, the result to other classes and show, for example, that the probabilistic complexity classes BPP, RP, and ZPP have many-one complete languages, provided that the set TAUT/sub 2/ of all valid /spl Pi//sub 2/-formulas in quantified propositional logic has a p-optimal proof system. Finally it is shown that already a collapse of tally sets at the double exponential time level implies the existence of a (p-)optimal proof system for TAUT.