Degrees of Dowd-type generic oracles

DOI10.1006/INCO.2002.3149MaRDI QIDQ1854543zbMATH OpenOpenAlexFDO

Authors Toshio Suzuki

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/ab3d694f334647e384388e653899cb8d2226134d

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Computable Dowd-type generic oracles
• Does truth-table of linear norm reduce the one-query tautologies to a random oracle?
• Forcing complexity: Minimum sizes of forcing conditions.
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Bounded truth table does not reduce the one-query tautologies to a random oracle

Cites work

• scientific article; zbMATH DE number 3950504 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 3652325 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1294498 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 841081 (Why is no real title available?)
• scientific article; zbMATH DE number 841088 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• A tight relationship between generic oracles and type-2 complexity theory
• Classical recursion theory. The theory of functions and sets of natural numbers
• Classical recursion theory. Vol. II
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Double jumps of minimal degrees
• Forcing and reducibilities
• Generic oracles, uniform machines, and codes
• On the random oracle hypothesis
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Some applications of forcing to hierarchy problems in arithmetic
• Some applications of the notions of forcing and generic sets
• Some observations on the probabilistic algorithms and NP-hard problems

Cited in

(8)

• Forcing complexity: Minimum sizes of forcing conditions.
• Resource-bounded martingales and computable Dowd-type generic sets
• Bounded truth table does not reduce the one-query tautologies to a random oracle
• A tight relationship between generic oracles and type-2 complexity theory
• 11th Asian Logic Conference
• Computable Dowd-type generic oracles
• Does truth-table of linear norm reduce the one-query tautologies to a random oracle?
• Generic oracles, uniform machines, and codes

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

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