Complexity of the \(r\)-query tautologies in the presence of a generic oracle
type: Item
instance of: scholarly article
title: Complexity of the \(r\)-query tautologies in the presence of a generic oracle
zbMATH Open document ID: 1015.03045
author: Toshio Suzuki
published in: Notre Dame Journal of Formal Logic
publication date: 2003-03-12T00:00:00Z
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1881631
zbMATH Keywords: arithmetical forcing
zbMATH Keywords: random oracle
zbMATH Keywords: computational complexity
zbMATH Keywords: generic oracle
zbMATH Keywords: Cantor space
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1038234608
OpenAlex ID: W2133854625
cites work: Q3220571
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: On bounded query machines
cites work: Q4321931
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: Bounded query machines: on NP and PSPACE
cites work: THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS
cites work: Generic oracles, uniform machines, and codes
cites work: Some applications of the notions of forcing and generic sets
cites work: Some applications of forcing to hierarchy problems in arithmetic
cites work: Q3905267
cites work: Set theory. An introduction to independence proofs
cites work: Forcing and reducibilities
cites work: Q3720579
cites work: Q5573961
cites work: Q4246600
cites work: On relativized probabilistic polynomial time algorithms
DOI: 10.1305/NDJFL/1038234608
Recommended article: A tight relationship between generic oracles and type-2 complexity theory
Recommended article: Complexity of Default Logic on Generalized Conjunctive Queries
Recommended article: Oracles and query lower bounds in generalised probabilistic theories
Recommended article: A general method to construct oracles realizing given relationships between complexity classes
Recommended article: Q5285981
Recommended article: Parameterized complexity of completeness reasoning for conjunctive queries
Recommended article: Q4955353
Recommended article: Q4283250
Recommended article: Q4376044
Recommended article: COMPUTABLE DOWD-TYPE GENERIC ORACLES
description: scientific article; zbMATH DE number 1881631