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

DOI10.2969/JMSJ/04430505zbMath0771.03014OpenAlexW2085378578MaRDI 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

densityrecursive setsminimal pairTuring machinelow setshonest polynomial Turing degreeshp-T-reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (1)

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

This page was built for publication: Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets