Random strings and truth-table degrees of Turing complete c.e. sets
type: Item
instance of: scholarly article
zbMATH Open document ID: 1314.03039
DOI: 10.2168/LMCS-10(3:15)2014
author: Mingzhong Cai
author: Rachel Epstein
author: Steffen Lempp
author: Joseph S. Miller
author: Rodney G. Downey
published in: Logical Methods in Computer Science
publication date: 2014-09-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/1408.5636
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 03D32
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6349734
zbMATH Keywords: random strings
zbMATH Keywords: truth-table degrees
zbMATH Keywords: strong reducibilities
zbMATH Keywords: minimal pair
MaRDI profile type: Publication
arXiv ID: 1408.5636
Recommended article: On the complexity of random strings
Recommended article: Q3033326
Recommended article: DEGREES OF RANDOMIZED COMPUTABILITY
Recommended article: On the polynomial depth of various sets of random strings
Recommended article: On the Polynomial Depth of Various Sets of Random Strings
Recommended article: Nonuniform complexity and the randomness of certain complete languages
Recommended article: Power of Randomization in Automata on Infinite Strings
Recommended article: Reductions to the set of random strings: the resource-bounded case
title: Random strings and truth-table degrees of Turing complete c.e. sets
reviewed by: Ludwig Staiger
description: scientific article; zbMATH DE number 6349734