Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (Q912625): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question / rank
 
Normal rank
Property / cites work
 
Property / cites work: Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounded query machines: on NP and PSPACE / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quantitative Relativizations of Complexity Classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounded query machines: on NP( ) and NPQUERY( ) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parity, circuits, and the polynomial-time hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: The knowledge complexity of interactive proof-systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Note on Randomized Polynomial Time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Every Prime Has a Succinct Certificate / rank
 
Normal rank

Latest revision as of 14:31, 20 June 2024

scientific article
Language Label Description Also known as
English
Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
scientific article

    Statements

    Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (English)
    0 references
    1989
    0 references
    query-time complexity
    0 references
    oracle queries
    0 references
    query-space complexity
    0 references
    Turing machines
    0 references
    separation
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references