Strong polynomial-time reducibility (Q676314)

If \(f\) and \(g\) are functions then \(f\leq_T^p g\) if there is a polynomial time algorithm, with access to oracle \(g\), that can compute \(f\). Take the set of all polynomial bounded functions (that is, they don't grow too fast). If \(f\leq_T^p g\) and \(g\leq_T^p f\) then we will say \(f\) and \(g\) are equivalent. This paper considers the structure of these equivalence classes (called degrees) under \(\leq_T^p\). In this paper the author shows that, for this structure, (1) if you look at all the degrees less than a given set, they do not form an upper semilattice, (2) a weak form of the exact pair theorem holds, (3) every degree is the sup of a minimal pair. The last result is in contrast to degrees of functions where a non-diamond theorem holds.