Index sets and parametric reductions |
| |
| Authors: | Rod G. Downey Michael R. Fellows |
| |
| Affiliation: | (1) School of Mathematical and Computing Sciences, P.O. Box 600, Victoria University, Wellington, New Zealand. e-mail: rod.downey@vuw.ac.nz, NZ;(2) Department of Computer Science, University of Victoria, Victoria, B.C. V8W 3P6, Canada. e-mail: mfellows@csr.uvic.ca, CA;(3) School of Mathematical and Computing Sciences, P.O. Box 600, Victoria University, Wellington, New Zealand. e-mail: mfellows@vuw.ac.nz, NZ |
| |
| Abstract: | We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W e ≤ q u A} for q∈ {m, T} are Σ4 0 complete. We also show hat FPT(≤ q n ), that is {e : W e computable and ≡ q n ?}, is Σ4 0 complete. We also look at computable presentability of these classes. Received: 13 July 1996 / Revised version: 14 April 2000 / Published online: 18 May 2001 |
| |
| Keywords: | Mathematics Subject Classification (2000): 03D15 03D30 68Q15 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
