##
**On polynomial-time bounded truth-table reducibility of NP sets to sparse sets.**
*(English)*
Zbl 0741.68049

For each reduction type \(r\), the concept of “\(\leq^ P_ r\)- reducibility to sparse sets” indicates a certain tractability notion. There are several types of polynomial time reductions \(r\): \(\leq^ P_ T\) (Turing reduction), \(\leq^ P_ m\) (many-one reduction), \(\leq^ P_{k-tt}\) (\(k\)-truth-table reduction), \(\leq^ P_{btt}\) ( bounded truth-table reduction), etc. It is known that:

(i) a set has polynomial size circuits iff it is \(\leq^ P_ T\)- reducible to a sparse set, and

(ii) if \(P\neq NP\) then no \(NP\)-complete set is \(\leq^ P_ m\)-reducible to a sparse set.

The aim of this paper is to extend this last result to \(\leq^ P_{btt}\)-reducibility (which is more general than \(\leq^ P_ T\)- reducibility). It is proved that if \(P\neq NP\) then \(NP\) has a set which is not \(\leq^ P_{btt}\)-reducible to any sparse set. It is also mentioned that the same technique allows one to prove that several number-theoretic problems (such as a factorization problem) either are in \(P\) or are not \(\leq^ P_{btt}\)-reducible to any sparse set, i.e., either these problems are tractable or are “hardly” intractable.

(i) a set has polynomial size circuits iff it is \(\leq^ P_ T\)- reducible to a sparse set, and

(ii) if \(P\neq NP\) then no \(NP\)-complete set is \(\leq^ P_ m\)-reducible to a sparse set.

The aim of this paper is to extend this last result to \(\leq^ P_{btt}\)-reducibility (which is more general than \(\leq^ P_ T\)- reducibility). It is proved that if \(P\neq NP\) then \(NP\) has a set which is not \(\leq^ P_{btt}\)-reducible to any sparse set. It is also mentioned that the same technique allows one to prove that several number-theoretic problems (such as a factorization problem) either are in \(P\) or are not \(\leq^ P_{btt}\)-reducible to any sparse set, i.e., either these problems are tractable or are “hardly” intractable.

Reviewer: S.P.Yukna (Vilnius)

### MSC:

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

03D15 | Complexity of computation (including implicit computational complexity) |

03D30 | Other degrees and reducibilities in computability and recursion theory |