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.

#### SCOPUS^{TM}

Citations

8
checked on Jul 31, 2020

#### WEB OF SCIENCE^{TM}

Citations

7
checked on Jul 24, 2020

#### Page view(s)

68
checked on Aug 1, 2020

#### Google Scholar^{TM}

Check
#### Altmetric

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