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

Ogiwara, Mitsunori; Watanabe, Osamu

SIAM J. Comput. 20, No. 3, 471-483 (1991).

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.

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

Keywords:

Berman-Hartmanis conjecture; polynomial-time hard sets; sparse sets; bounded truth-table reduction