Complexity of the \(r\)-query tautologies in the presence of a generic oracle

DOI10.1305/ndjfl/1038234608zbMath1015.03045OpenAlexW2133854625MaRDI QIDQ1861135

Toshio Suzuki

Publication date: 12 March 2003

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1038234608

zbMATH Keywords

computational complexityCantor spacerandom oraclegeneric oraclearithmetical forcing

Mathematics Subject Classification ID

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

Related Items

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?, Degrees of Dowd-type generic oracles, Resource-bounded martingales and computable Dowd-type generic sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On bounded query machines
• Set theory. An introduction to independence proofs
• Bounded query machines: on NP and PSPACE
• Generic oracles, uniform machines, and codes
• On relativized probabilistic polynomial time algorithms
• Forcing and reducibilities
• 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 the notions of forcing and generic sets
• Some applications of forcing to hierarchy problems in arithmetic
• THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS