Nonexistence of minimal pairs for generic computability

DOI10.2178/jsl.7802090zbMath1302.03048arXiv1202.2560OpenAlexW2024128940MaRDI QIDQ5300075

Gregory Igusa

Publication date: 24 June 2013

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

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

zbMATH Keywords

generic computability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (11)

Notions of robust information coding ⋮ Asymptotic density, immunity and randomness ⋮ THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ 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 COMPUTABLY ENUMERABLE SETS ⋮ Asymptotic density and the coarse computability bound ⋮ Generic case completeness ⋮ 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
• Average Case Complete Problems
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS

This page was built for publication: Nonexistence of minimal pairs for generic computability