Pages that link to "Item:Q912625"
From MaRDI portal
The following pages link to Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (Q912625):
Displaying 24 items.
- Helping by unambiguous computation and probabilistic computation (Q675865) (← links)
- On the P versus NP intersected with co-NP question in communication complexity (Q1044738) (← links)
- On random oracle separations (Q1182108) (← links)
- Separating complexity classes with tally oracles (Q1185002) (← links)
- Polynomial-time compression (Q1198955) (← links)
- The relative complexity of NP search problems (Q1273858) (← links)
- Randomized Boolean decision trees: Several remarks (Q1275008) (← links)
- Exact lower time bounds for computing Boolean functions on CREW PRAMs (Q1329159) (← links)
- A tight relationship between generic oracles and type-2 complexity theory (Q1369098) (← links)
- Complexity measures and decision tree complexity: a survey. (Q1853508) (← links)
- On the complexity of finding a local maximum of functions on discrete planar subsets (Q1884980) (← links)
- Arthur-Merlin games in Boolean decision trees (Q1961380) (← links)
- Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives (Q2220875) (← links)
- Time and space complexity of deterministic and nondeterministic decision trees (Q2679423) (← links)
- Improved bounds for the randomized decision tree Complexity of recursive majority (Q2811168) (← links)
- Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority (Q3012816) (← links)
- The Dual BKR Inequality and Rudich's Conjecture (Q3081331) (← links)
- Structural properties for feasibly computable classes of type two (Q4009811) (← links)
- Fault-tolerance and complexity (Extended abstract) (Q4630260) (← links)
- A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$ (Q5117375) (← links)
- Separation Between Deterministic and Randomized Query Complexity (Q5376437) (← links)
- (Q5874464) (← links)
- Quadratically tight relations for randomized query complexity (Q5915578) (← links)
- On (simple) decision tree rank (Q6050134) (← links)
