Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets

From MaRDI portal





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.




Cited in
(53)








This page was built for publication: Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3978778)