On polynomial time one-truth-table reducibility to a sparse set
type: Item
instance of: scholarly article
title: On polynomial time one-truth-table reducibility to a sparse set
zbMATH Open document ID: 0746.68036
DOI: 10.1016/0022-0000(92)90015-B
author: Osamu Watanabe
published in: Journal of Computer and System Sciences
publication date: 1992-09-27T00:00:00Z
review text: 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 exte…
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 58913
zbMATH Keywords: relations among complexity classes
zbMATH Keywords: reducibility
zbMATH Keywords: structural complexity
reviewed by: Martin Kummer
MaRDI profile type: Publication
cites work: Q3747725
cites work: Q3692867
cites work: On Sets Truth-Table Reducible to Sparse Sets
cites work: Cryptocomplexity and NP-completeness
cites work: A Note on Sparse Complete Sets
cites work: Q4198056
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: On some natural complete operators
cites work: On one-way functions and polynomial-time isomorphisms
cites work: Collapsing degrees
cites work: A comparison of polynomial time reducibilities
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: The complexity of facets (and some facets of complexity)
cites work: Complete sets and closeness to complexity classes
cites work: Natural Self-Reducible Sets
cites work: Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
cites work: Relative complexity of checking and evaluating
cites work: NP is as easy as detecting unique solutions
cites work: On hardness of one-way functions
cites work: On intractability of the classUP
cites work: Complete sets and the polynomial-time hierarchy
cites work: On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
description: scientific article; zbMATH DE number 58913