Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (Q912625)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? |
scientific article; zbMATH DE number 4145338
| 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; zbMATH DE number 4145338 |
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
