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

Book, Ronald V.; Ko, Ker-I

SIAM J. Comput. 17, No. 5, 903-919 (1988).

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

Keywords:

truth-table reducibility; sparse sets; tally sets; polynomial-size circuits