Title :
On polynomial time bounded truth-table reducibility of NP sets to sparse sets
Author :
Ogiwara, Mitsunori ; Watanabe, Osamu
Author_Institution :
Tokyo Inst. of Technol., Japan
Abstract :
Summary form only given. It is proved that if P≠NP, then there exits a set in NP that is polynomial-time bounded truth-table reducible to no sparse set. By using the technique proving this result, intractability of several number theoretic decision problems, i.e. decision problems defined naturally from number theoretic problems, is investigated. It is shown that for those number theoretic decision problems, if it is not in P, then it is polynomial-time bounded truth-table reducible to no sparse set
Keywords :
computational complexity; set theory; NP sets; P≠NP; intractability; number theoretic decision problems; polynomial time bounded truth-table reducibility; sparse sets; Computer science; Polynomials;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113948
