Degrees of Dowd-type generic oracles

DOI10.1006/inco.2002.3149zbMath1012.03052OpenAlexW1982156324MaRDI QIDQ1854543

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

11th Asian Logic Conference ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ Forcing complexity: Minimum sizes of forcing conditions. ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Resource-bounded martingales and computable Dowd-type generic sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some observations on the probabilistic algorithms and NP-hard problems
• Generic oracles, uniform machines, and codes
• Classical recursion theory. The theory of functions and sets of natural numbers
• A comparison of polynomial time reducibilities
• Classical recursion theory. Vol. II
• A tight relationship between generic oracles and type-2 complexity theory
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Forcing and reducibilities
• 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
• Double jumps of minimal degrees
• Some applications of the notions of forcing and generic sets
• Some applications of forcing to hierarchy problems in arithmetic

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