Archive for Mathematical Logic 40 (5):329-348 (2001)
| 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
|
| Keywords | Key words or phrases: Index set – Parameterized complexity |
| Categories |
No categories specified (categorize this paper) |
| DOI | 10.1007/s001530100082 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
PhilArchive copy
Upload a copy of this paper Check publisher's policy Papers currently archived: 56,903
External links
- From the Publisher via CrossRef (no proxy)
- citeseerx.ist.psu.edu
(no proxy) - link.springer.com (no proxy)
- link.springer.com [2] (no proxy)
- mrfellows.net (no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
- Sign in / register and customize your OpenURL resolver..
- Configure custom resolver
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Index Sets for Classes of High Rank Structures.W. Calvert, E. Fokina, S. S. Goncharov, J. F. Knight, O. Kudinov, A. S. Morozov & V. Puzarenko - 2007 - Journal of Symbolic Logic 72 (4):1418 - 1432.
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.
Boolean Algebras, Tarski Invariants, and Index Sets.Barbara F. Csima, Antonio Montalbán & Richard A. Shore - 2006 - Notre Dame Journal of Formal Logic 47 (1):1-23.
Review: Louise Hay, On Creative Sets and Indices of Partial Recursive Functions; Louise Hay, Isomorphism Types of Index Sets of Partial Recursive Functions; Louise Hay, Index Sets of Finite Classes of Recursively Enumerable Sets. [REVIEW]Forbes D. Lewis - 1974 - Journal of Symbolic Logic 39 (1):186-187.
The Algebraic Structure of the Isomorphic Types of Tally, Polynomial Time Computable Sets.Yongge Wang - 2002 - Archive for Mathematical Logic 41 (3):215-244.
The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑5‐Complete.Stephan Wehner - 1994 - Mathematical Logic Quarterly 40 (1):87-94.
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.
A Note on the Computation of the Mean Random Consistency Index of the Analytic Hierarchy Process (Ahp).V. M. Rao Tummala & Hong Ling - 1998 - Theory and Decision 44 (3):221-230.
On the Degrees of Diagonal Sets and the Failure of the Analogue of a Theorem of Martin.Keng Meng Ng - 2009 - Notre Dame Journal of Formal Logic 50 (4):469-493.
Analytics
Added to PP index
2013-11-23
Total views
27 ( #384,501 of 2,409,456 )
Recent downloads (6 months)
4 ( #189,392 of 2,409,456 )
2013-11-23
Total views
27 ( #384,501 of 2,409,456 )
Recent downloads (6 months)
4 ( #189,392 of 2,409,456 )
How can I increase my downloads?
Downloads
