Premium
Do there exist complete sets for promise classes?
Author(s) -
Beyersdorff Olaf,
Sadowski Ze
Publication year - 2011
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201010021
Subject(s) - advice (programming) , physics , combinatorics , mathematics , computer science , programming language
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