Do there exist complete sets for promise classes?
Olaf Beyersdorff, Zenon Sadowski · Mathematical logic quarterly · 2011
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