Pages that link to "Item:Q3734382"
From MaRDI portal
The following pages link to Quantitative Relativizations of Complexity Classes (Q3734382):
Displaying 34 items.
- Tractable counting of the answers to conjunctive queries (Q389242) (← links)
- The consequences of eliminating NP solutions (Q458458) (← links)
- The strong exponential hierarchy collapses (Q584250) (← links)
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- The shrinking property for NP and coNP (Q627189) (← links)
- Optimal advice (Q672755) (← links)
- Nondeterministic functions and the existence of optimal proof systems (Q837177) (← links)
- Pseudorandom generators against advised context-free languages (Q899305) (← links)
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (Q912625) (← links)
- Robust machines accept easy sets (Q914369) (← links)
- Qualitative relativizations of complexity classes (Q1061119) (← links)
- Robust algorithms: a different approach to oracles (Q1063417) (← links)
- On some natural complete operators (Q1064780) (← links)
- On bounded query machines (Q1085975) (← links)
- Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) (Q1094139) (← links)
- On sparse oracles separating feasible complexity classes (Q1111385) (← links)
- Positive relativizations of the \(P=?\) NP problem (Q1124342) (← links)
- Strong and robustly strong polynomial-time reducibilities to sparse sets (Q1177170) (← links)
- Turing machines with few accepting computations and low sets for PP (Q1190987) (← links)
- On hiding information from an oracle (Q1263281) (← links)
- A note on sparse sets and the polynomial-time hierarchy (Q1263964) (← links)
- A hierarchy based on output multiplicity (Q1274991) (← links)
- A taxonomy of complexity classes of functions (Q1329166) (← links)
- Functions computable with limited access to NP (Q1351162) (← links)
- Inverting onto functions. (Q1426007) (← links)
- Exact learning via teaching assistants (Q1575459) (← links)
- Reducing the number of solutions of NP functions (Q1608321) (← links)
- Sets with small generalized Kolmogorov complexity (Q1821559) (← links)
- Bounded queries, approximations, and the Boolean hierarchy (Q1854449) (← links)
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. (Q1872705) (← links)
- Reductions between disjoint NP-pairs (Q2387199) (← links)
- Positive relativizations for log space computability (Q2639638) (← links)
- Cluster computing and the power of edge recognition (Q2643084) (← links)
- Solutions to twisted word equations and equations in virtually free groups (Q3299596) (← links)
