# zbMATH — the first resource for mathematics

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.

##### 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
Full Text: