Do there exist complete sets for promise classes?

✍ Scribed by Olaf Beyersdorff; Zenon Sadowski

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 203 KB
• Volume: 57
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.201010021

✦ Synopsis

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 ∩ 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. For promise classes with promise condition in coNP, the advice can be replaced by a tally NP-oracle.