On Sets Bounded Truth-Table Reducible to P-selective Sets

Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe

We show that if every NP set is polynomial-time bounded truth-table reducible to some P-selective set, then NP is contained in $\DTIME(2^{n^{O(1/\sqrt{\log n})}})$. In the proof, we implement a recursive procedure that reduces the number of nondeterministic steps of a given nondeterministic computation.