Archive for Mathematical Logic 40 (5):329-348 (2001)

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
Keywords Key words or phrases: Index set – Parameterized complexity
Categories No categories specified
(categorize this paper)
DOI 10.1007/s001530100082
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 69,979
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Kleene Index Sets and Functional M-Degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Index Sets for Ω‐Languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - Mathematical Logic Quarterly 49 (1):22-33.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
Lusin-Sierpinski Index for the Internal Sets.Boško Živaljević - 1992 - Journal of Symbolic Logic 57 (1):172 - 178.
Index Sets of Finite Classes of Recursively Enumerable Sets.Louise Hay - 1969 - Journal of Symbolic Logic 34 (1):39-44.


Added to PP index

Total views
27 ( #422,825 of 2,504,866 )

Recent downloads (6 months)
1 ( #417,030 of 2,504,866 )

How can I increase my downloads?


My notes