A MINIMAL SET LOW FOR SPEED

DOI10.1017/jsl.2021.108OpenAlexW4205949975MaRDI QIDQ5052019

Matthew Harrison-Trainor, Rodney G. Downey

Publication date: 18 November 2022

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

minimal degreelow for speed

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other Turing degree structures (03D28)

Cites Work

• Limits on the computational power of random strings
• On low for speed oracles
• What can be efficiently reduced to the Kolmogorov-random strings?
• Random strings and tt-degrees of Turing complete C.E. sets
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

This page was built for publication: A MINIMAL SET LOW FOR SPEED