Do there exist complete sets for promise classes?

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 \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {C}$\end{document} ? For concrete languages L (such as TAUT or SAT) and concrete promise classes \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {C}$\end{document} (such as \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {NP}\cap \mathsf {co}\mathsf {NP}$\end{document} , \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {UP}$\end{document} , \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {BPP}$\end{document} , disjoint \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {NP}$\end{document} ‐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 \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {C}$\end{document} 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 \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {co}$\end{document} \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {NP}$\end{document} , the advice can be replaced by a tally \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {NP}$\end{document} ‐oracle. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim