A MINIMAL SET LOW FOR SPEED

DOI10.1017/JSL.2021.108MaRDI QIDQ5052019zbMATH OpenOpenAlexFDO

Authors Matthew Harrison-Trainor, Rodney G. Downey

Publication date 18 November 2022

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

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

zbMATH Keywords

low for speedminimal degree

Mathematics Subject Classification ID

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

Recommendations

• On low for speed oracles
• On low for speed oracles
• Being low along a sequence and elsewhere
• Constructing minimal pairs of degrees
• Minimal generalized computable enumerations and high degrees

Cites work

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

Cited in

(2)

• On low for speed oracles
• A minimal set low for speed

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5052019)