Do there exist complete sets for promise
✍
Olaf Beyersdorff; Zenon Sadowski
📂
Article
📅
2011
🏛
John Wiley and Sons
🌐
English
⚖ 203 KB
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, dis