On the maximality of some pairs of p-t degrees (Q689190)

This paper discusses the properties of polynomial time degrees. It is shown that there are recursive p-t degrees \(\underset\widetilde{} a>\underset\widetilde{} a_ 0\) and \(\underset\widetilde{} b>\underset\widetilde{} b_ 0\), for any recursive p-t degrees \(\underset\widetilde{} a_ 0\) and \(\underset\widetilde{} b_ 0\), such that \(\{\underset\widetilde{} a,\underset\widetilde{} b\}\) and \(\{\underset\widetilde{} a_ 0,\underset\widetilde{} b_ 0\}\) have the same lower bound set of the degrees. Hence, there is neither maximal minimal pair, maximal exact pair, nor maximal branching pair of p-t degrees.