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

DOI10.2969/jmsj/04430505zbMath0771.03014MaRDI QIDQ1201781

Teruko Tsuda, Juichi Shinoda, Kunimasa Aoki

Publication date: 17 January 1993

Published in: Journal of the Mathematical Society of Japan (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2969/jmsj/04430505

zbMATH Keywords

density; recursive sets; minimal pair; Turing machine; low sets; honest polynomial Turing degrees; hp-T-reducibility

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D25: Recursively (computably) enumerable sets and degrees

03D30: Other degrees and reducibilities in computability and recursion theory

Related Items

On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets