Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Johannes Köbler and Jochen Messner

Abstract:

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 the intersection of NP and 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, e.g., that the probabilistic complexity classes BPP, RP, and ZPP have many-one complete languages, provided that the set TAUT_2 of all valid Pi_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.

The copyright policy of IEEE obliges us to add the following copyright notice. For those who read this notice we just want to mention that the date given below is incorrect (the conference took place in June).

Copyright 1998 IEEE. Published in the Proceedings of Complexity'98, April 15-18, 1998 in Buffalo, New York. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works, must be obtained from the IEEE. Contact: Manager, Copyrights and Permissions / IEEE Service Center / 445 Hoes Lane / P.O. Box 1331 / Piscataway, NJ 08855-1331, USA. Telephone: + Intl. 908-562-3966.