Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets (Q1201781)

The authors prove two theorems about the so-called honest polynomial Turing degrees (hp-T-degrees). hp-T-reducibility \((\leq_ T^ h)\) is a kind of polynomial one designed to classify sets of finite sequences of \(\{0,1\}\) according to their algorithmic complexity. The affirmative answer to the question about the density of hp-T-degrees of \(\Delta_ 2^ 0\) sets implies P\(\neq\)NP. The first theorem asserts that for any recursive sets \(A\) and \(B\), \(B<_ T^ h A\), there exist sets \(C\) and \(D\) such that \(B<_ T^ h C<_ T^ h A\), \(B<_ T^ h D<_ T^ h A\) and \(C\cap D\equiv_ T^ h B\). So this theorem combines the density theorem with the minimal pair theorem. The second theorem is a generalization of the first one for the case of \(\Delta_ 2^ 0\) low sets instead of recursive sets. The proofs of both theorems are simple and use the ``looking back'' technique of Ladner. In the proof of the second theorem, a recursive approximation of \(\Delta_ 2^ 0\) low sets is applied.