Strong minimal pair theorem for the honest polynomial degrees of \(\Delta{}^ 0_ 2\) low sets
From MaRDI portal
Publication:1201781
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
density; recursive sets; minimal pair; Turing machine; low sets; honest polynomial Turing degrees; hp-T-reducibility
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