Random strings and tt-degrees of Turing complete C.E. sets

DOI10.2168/LMCS-10(3:15)2014zbMath1314.03039arXiv1408.5636MaRDI QIDQ2921112

Steffen Lempp, Joseph S. Miller, Rachel Epstein, Mingzhong Cai, Rodney G. Downey

Publication date: 30 September 2014

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.5636

zbMATH Keywords

minimal pairtruth-table degreesrandom stringsstrong reducibilities

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32)

Related Items (4)

A MINIMAL SET LOW FOR SPEED ⋮ Some games on Turing machines and power from random strings ⋮ The Complexity of Complexity ⋮ On low for speed oracles

This page was built for publication: Random strings and tt-degrees of Turing complete C.E. sets