On polynomial time one-truth-table reducibility to a sparse set (Q1191028): Difference between revisions

A set \(S\) of strings is called sparse iff there is a polynomial \(p\) such that \(S\) contains at most \(p(n)\) elements of length \(n\), for every \(n\geq 0\). For an intractable complexity class \({\mathcal C}\) (i.e. \({\mathcal C}\not\subseteq P\)) and a notion of reducibility one can ask whether \({\mathcal C}\) contains a set that is reducible to no sparse set. This has been one of the major themes of structural complexity theory in the last years. The author considers this question for (polynomial time) \(1-tt\)- reducibility and for complexity classes \({\mathcal C}\) that are related to the existence of one-way functions: \({\mathcal C}=UP,\;FewP,\;UBPP,\;{\mathcal UP},\;NP\). If a set \(A\) is \(1-tt\)-reducible to no sparse set then there does not exist a certain type of ``approximation algorithm'' for \(A\). The main achievement of the paper is an extension of a method of \textit{S. R. Mahaney} [J. Comput. Syst. Sci. 25, 130-143 (1982; Zbl 0493.68043)], that enables the author to prove, for \({\mathcal C}=UP,\;UBBP,\;{\mathcal UP}\), that if \({\mathcal C}\) is intractable then \({\mathcal C}\) contains a set that is \(1- tt\)-reducible to no sparse set. As a corollary he obtains that \(NP\) has no sparse \(1-tt\)-hard set if \(R\neq NP\). If is left open whether in this statement \(R\) can be replaced by \(P\), and also wether \(P\neq FewP\) implies that \(FewP\) has a set that is \(1-tt\) reducible to no sparse set. Recently \textit{M. Ogiware} and the author have discovered a much more powerful method [On polynomial time bounded truth-table reducibility of \(NP\) sets to sparse sets, Proc. of the 22nd ACM Symp. on the Theory of Computing, New York, 457-467 (1990)]; for a nice simplified proof see also: \textit{S. Homer} and \textit{L. Longpré} [On reductions of \(NP\) sets to sparse sets, Proc. of the 6th Annual Structure in Complexity Theory Conference, Los Alamitos, 79-88 (1991)]. As a direct consequence, the results of the paper under review extend from \(1-tt\)- to \(btt\)- reducibility, and the open questions, for \({\mathcal C}=FewP,\;NP\), are now answered positively.