Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets
type: Item
instance of: scholarly article
title: Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets
zbMATH Open document ID: 0771.03014
author: Kunimasa Aoki
author: Juichi Shinoda
author: Teruko Tsuda
published in: Journal of the Mathematical Society of Japan
publication date: 1993-01-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 98461
zbMATH Keywords: Turing machine
zbMATH Keywords: honest polynomial Turing degrees
zbMATH Keywords: hp-T-reducibility
zbMATH Keywords: density
zbMATH Keywords: minimal pair
zbMATH Keywords: low sets
zbMATH Keywords: recursive sets
reviewed by: Sh. T. Ishmukhametov
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.2969/jmsj/04430505
OpenAlex ID: W2085378578
DOI: 10.2969/JMSJ/04430505
description: scientific article; zbMATH DE number 98461