Complexity of the \(r\)-query tautologies in the presence of a generic oracle
From MaRDI portal
Publication:1861135
DOI10.1305/NDJFL/1038234608zbMath1015.03045OpenAlexW2133854625MaRDI QIDQ1861135
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
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (5)
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
This page was built for publication: Complexity of the \(r\)-query tautologies in the presence of a generic oracle
