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.


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: DOI