Thomas Thierauf, Seinosuke Toda, and Osamu Watanabe
Abstract:
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.