THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS

DOI10.1017/jsl.2014.77zbMath1367.03077arXiv1402.3747OpenAlexW1547199729MaRDI QIDQ2795919

Gregory Igusa

Publication date: 22 March 2016

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

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

zbMATH Keywords

degreehyperarithmetic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (6)

A generic relation on recursively enumerable sets ⋮ A MINIMAL PAIR IN THE GENERIC DEGREES ⋮ DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES ⋮ Asymptotic Density and the Theory of Computability: A Partial Survey ⋮ Some Questions in Computable Mathematics ⋮ Asymptotic density and computability

Cites Work

• Average case completeness
• Generic-case complexity, decision problems in group theory, and random walks.
• Generic computability, Turing degrees, and asymptotic density
• Unnamed Item

This page was built for publication: THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS