On Sets Cook-Reducible to Sparse Sets

Previous article Next article On Sets Cook-Reducible to Sparse SetsRobert M. SolovayRobert M. Solovayhttps://doi.org/10.1137/0205043PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractLynch showed that any set many-one reducible in polynomial time to arbitrarily sparse sets is polynomial time computable. We prove the analogous theorem for polynomial time Turing reproducibility.[1] Theodore Baker, , John Gill and , Robert Solovay, Relativizations of the P=? N P question, SIAM J. Comput., 4 (1975), 431–442 10.1137/0204037 MR0395311 0323.68033 LinkGoogle Scholar[2] Nancy Lynch, On reducibility to complex or sparse sets, J. Assoc. Comput. Mach., 22 (1975), 341–345 MR0379150 0311.68037 CrossrefISIGoogle ScholarKeywordspolynomial time computableTuring reducibility Previous article Next article FiguresRelatedReferencesCited byDetails On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse SetsYaacov Yesha13 July 2006 | SIAM Journal on Computing, Vol. 12, No. 3AbstractPDF (1726 KB) Volume 5, Issue 4| 1976SIAM Journal on Computing History Submitted:13 February 1975Published online:13 July 2006 InformationCopyright © 1976 Society for Industrial and Applied MathematicsKeywordspolynomial time computableTuring reducibilityPDF Download Article & Publication DataArticle DOI:10.1137/0205043Article page range:pp. 646-652ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics