Nondiamond theorems for polynomial time reducibility

摘要

We investigate the structure of recursive sets under polynomial time Turing reducibility. In particular, we solve a question of Ambos-Spies by constructing a polynomial time degree that is not the supremum of a minimal pair. The proof is of some technical interest as it uses π2 priority arguments and the speedup phenomenon.