Computable Dowd-type generic oracles

DOI10.1142/9789814360548_0008MaRDI QIDQ4922664zbMATH OpenOpenAlexFDO

Authors Masahiro Kumabe, Toshio Suzuki

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 complexityDowd-genericityeffective randomnessgeneric oraclesrelativization

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Generic absoluteness and forcing axioms (03E57) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Degrees of Dowd-type generic oracles
• Generic oracles, uniform machines, and codes
• Forcing complexity: Minimum sizes of forcing conditions.
• Resource-bounded martingales and computable Dowd-type generic sets
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle

Cited in

(14)

• Generic oracles, uniform machines, and codes
• The generic oracle hypothesis is false
• Dynamic notions of genericity and array noncomputability
• A tight relationship between generic oracles and type-2 complexity theory
• An oracle builder's toolkit
• Forcing complexity: Minimum sizes of forcing conditions.
• Degrees of Dowd-type generic oracles
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Computability with two-place oracle
• Resource-bounded martingales and computable Dowd-type generic sets
• Weak randomness, genericity and Boolean decision trees
• scientific article; zbMATH DE number 4025422 (Why is no real title available?)
• scientific article; zbMATH DE number 1191231 (Why is no real title available?)
• Relativized generic classes P and NP

This page was built for publication: Computable Dowd-type generic oracles

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