On the maximality of some pairs of p-t degrees.
Xi Zhong Zheng · Notre Dame Journal of Formal Logic · 1992
This paper discusses the properties of polynomial time Turing degrees.It is shown that there exist recursive p-t degrees a > a 0 and b > b 0 , for any recursive p-t degrees a 0 and b 0 , such that [a,b] and {a o ,b o } have the same low bound set of the degrees.Hence, there is neither maximal minimal pair, maximal exact pair, nor maximal branching pair of p-t degrees.Zheng [7] proved that there is no maximal p-m minimal pair.This paper will show a similar (in fact somewhat more general) result about p-t degrees.The concept of the polynomial time Turing reducibility (abbrev.p-t reducibility) was introduced by Cook in [3].A set A is polynomial time Turing reducible to B (denoted by A <f B) if there is a polynomial time bounded Turing machine M B with oracle B such that M B accepts A. A is p-t equivalent to B if A <? B and B <? A, which is denoted by A s£ B. The p-t degree of set A (denoted by deg(^4)) is the class of all sets that are equivalent to A 9 i.e., deg(A) = [B:A =t B).Below, the p-t degrees are denoted by a,b,c 9 For any p-t degrees a and b 9 a is called (p-t) reducible to b (denoted by a < b) if there are sets A EL a and B E b such that A