On sets truth-table reducible to sparse sets. (English) Zbl 0665.68040

For a polynomial time reducibility \(\leq^ P_ r\) and a class \({\mathcal C}\) of languages one defines \(P_ r({\mathcal C})=\{A : A\leq^ P_ rX\) for some \(X\in {\mathcal C}\}\). r may be m (many-one), tt (truth-table), btt (bounded truth-table) or k-tt (truth table with k variables, k a positive integer). The main results of the paper are:
(1)The \(P_{k-tt}\) (SPARSE) form a proper infinite hierarchy with respect to k.
(2)\(P_{btt}\) (SPARSE) is properly contained in \(P_{tt}\) (SPARSE).
(3)\(P_{tt}(TALLY)=P_{tt}\) \((SPARSE)=P/poly\) \((=the\) class of sets having polynomial-size circuits).
(4)\(P_{btt}(TALLY)=P_ m(TALLY)\).
Reviewer: G.Wechsung


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D30 Other degrees and reducibilities in computability and recursion theory
Full Text: DOI