Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-081 | 27th August 2009 10:57

Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes


Authors: Olaf Beyersdorff, Zenon Sadowski
Publication: 22nd September 2009 19:54
Downloads: 1492


In this paper we investigate the following two questions:

Q1: Do there exist optimal proof systems for a given language L?
Q2: Do there exist complete problems for a given promise class C?

For concrete languages L (such as TAUT or SAT and concrete promise classes C (such as NP $\cap$ coNP, UP, BPP, disjoint NP-pairs etc.), these questions have been intensively studied during the last years, and a number of characterizations have been obtained. Here we provide new characterizations for Q1 and Q2 that apply to almost all promise classes $\C$ and languages $L$, thus creating a unifying
framework for the study of these practically relevant questions.

While questions Q1 and Q2 are left open by our results, we show that they receive affirmative answers when a small amount of advice is available in the underlying machine model. This continues a recent line of research on proof systems with advice started by Cook and Krajicek.

ISSN 1433-8092 | Imprint