학술논문
On sets bounded truth-table reducible to ${\rm P}$-selective sets.
Document Type
Proceedings Paper
Author
Thierauf, Thomas (D-ULM-TI) AMS Author Profile; Toda, Seinosuke (J-CHOF-C) AMS Author Profile; Watanabe, Osamu (J-TOKYTE-C) AMS Author Profile
Source
Subject
03 Mathematical logic and foundations -- 03D Computability and recursion theory
03D15Complexity of computation
68Computer science -- 68Q Theory of computing
68Q15Complexity classes
03D15
68
68Q15
Language
English
Abstract
Summary: ``We show that if every NP set is $\leq^{\rm P}_{\rm btt}$-reducible to some P-selective set, then NP is contained in DTIME$(2^{n^{(1/\sqrt{\log n})}})$. This result is extended to some unbounded reducibilities, such as $\leq^{\rm P}_{\rm polylog\text{-}tt}$-reducibility.''