Undecidability and Definability for Parametrized Polynomial Time m-Reducibilities
Peter A. Cholak, Rodney G. Downey · Birkhäuser Boston eBooks · 1993
In the setting of the parametrized reducibilities introduced by the second author and Mike Fellows, we prove a number of decidability and definability results. In particular the undecidability of the relevant m-degree structures is proven. The relationship with classical notions is analyzed, and this leads to a number of observations about classical constructions in the PTIME degrees. Methods include 0″, 0″′ and 0 (4) priority arguments combined with speedup type arguments.