## 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

### MSC:

 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: