Relating equivalence and reducibility to sparse sets. (English) Zbl 0761.68039

Summary: For various polynomial-time reducibilities \(r\), this paper asks whether being \(r\)-reducible to a sparse set is a broader notion than being \(r\)- equivalent to a sparse set. Although distinguishing equivalence and reducibility to sparse sets, for many-one or 1-truth-table reductions, would imply that \(P\neq NP\), this paper shows that for \(k\)-truth-table reductions, \(k\geq 2\), equivalence and reducibility to sparse sets provably differ. Though R. Gavaldà and O. Watanabe [On the computational complexity of small descriptions, in Proc. 6th Structure in Complexity Theory Conference, IEEE Computer Society Press, June/July 1991, 89-101 (1991)] have shown that, for any polynomial-time computable unbounded function \(f(\cdot)\), some sets \(f(n)\)-truth-table reducible to sparse sets are not even Turing equivalent to sparse sets, this paper shows that extending their result to the 2-truth-table case would provide a proof that \(P\neq NP\). Additionally, this paper studies the relative power of different notions of reducibility, and proves that disjunctive and conjunctive truth-table reductions to sparse sets are surprisingly powerful, refuting a conjecture of K. Ko [Inf. Comput. 81, No. 1, 62-87 (1989; Zbl 0681.68066)].


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D30 Other degrees and reducibilities in computability and recursion theory
03D55 Hierarchies of computability and definability


Zbl 0681.68066
Full Text: DOI Link