Please use this identifier to cite or link to this item: https://doi.org/10.1109/CCC.2007.17
Title: On C-degrees, H-degrees and T-degrees
Authors: Merkle, W.
Stephan, F. 
Issue Date: 2007
Citation: Merkle, W., Stephan, F. (2007). On C-degrees, H-degrees and T-degrees. Proceedings of the Annual IEEE Conference on Computational Complexity : 60-69. ScholarBank@NUS Repository. https://doi.org/10.1109/CCC.2007.17
Abstract: Following a line of research that aims at relating the computation power and the initial segment complexity of a set, the work presented here investigates into the relations between Turing reducibility, defined in terms of computation power, and C-reducibility and H-reducibility, defined in terms of the complexity of initial segments. The global structures of all C-degrees and of all H-degrees are rich and allows to embed the lattice of the power set of the natural numbers under inclusion. In particular, there are C-degrees, as well as H-degrees, that are different from the least degree and are the meet of two other degrees, whereas on the other hand there are pairs of sets that have a meet neither in the C-degrees nor in the H-degrees; these results answer questions in a survey by Nies and Miller. There are r.e. sets that form a minimal pair for C-reducibility and ∑2 0 sets that form a minimal pair for H-reducibility, which answers questions by Downey and Hirschfeldt. Furthermore, the following facts on the relation between C-degrees, H-degrees and Turing degrees hold. Every C-degree contains at most one Turing degree and this bound is sharp since there are C-degrees that do contain a Turing degree. For the comprising class of complex sets, neither the C-degree nor the H-degree of such a set can contain a Turing degree, in fact, the Turing degree of any complex set contains infinitely many C-degrees. Similarly the Turing degree of any set that computes the halting problem contains infinitely many H-degrees, while the H-degree of any 2-random set R is never contained in the Turing degree of R. By the latter, H-equivalence of Martin-Löf random sets does not imply their Turing equivalence. The structure of the C-degrees contained in the Turing degree of a complex sets is rich and allows to embed any countable distributive lattice; a corresponding statement is true for the structure of H-degrees that are contained in the Turing degree of a set that computes the halting problem. © 2007 IEEE.
Source Title: Proceedings of the Annual IEEE Conference on Computational Complexity
URI: http://scholarbank.nus.edu.sg/handle/10635/104598
ISBN: 0769527809
ISSN: 10930159
DOI: 10.1109/CCC.2007.17
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

8
checked on Jul 31, 2020

WEB OF SCIENCETM
Citations

7
checked on Jul 24, 2020

Page view(s)

68
checked on Aug 1, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.