COMPUTABLE DOWD-TYPE GENERIC ORACLES

DOI10.1142/9789814360548_0008zbMath1280.03046MaRDI QIDQ4922664

Toshio Suzuki, Masahiro Kumabe

Publication date: 3 June 2013

Published in: Proceedings of the 11th Asian Logic Conference (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/9789814360548_0008

zbMATH Keywords

computational complexity; relativization; effective randomness; generic oracles; Dowd-genericity

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D20: Recursive functions and relations, subrecursive hierarchies

03D30: Other degrees and reducibilities in computability and recursion theory

03D32: Algorithmic randomness and dimension

03E57: Generic absoluteness and forcing axioms

Related Items

Resource-bounded martingales and computable Dowd-type generic sets