Pages that link to "Item:Q1055405"
From MaRDI portal
The following pages link to Strong nondeterministic polynomial-time reducibilities (Q1055405):
Displaying 38 items.
- The consequences of eliminating NP solutions (Q458458) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- Some results on selectivity and self-reducibility (Q672402) (← links)
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes (Q809600) (← links)
- Robust machines accept easy sets (Q914369) (← links)
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly (Q1029043) (← links)
- Qualitative relativizations of complexity classes (Q1061119) (← links)
- The recursion-theoretic structure of complexity classes (Q1064320) (← links)
- Decompositions of nondeterministic reductions (Q1108263) (← links)
- Graph isomorphism is in the low hierarchy (Q1116696) (← links)
- A uniform approach to obtain diagonal sets in complexity classes (Q1164414) (← links)
- Reductions on NP and p-selective sets (Q1166515) (← links)
- Strong and robustly strong polynomial-time reducibilities to sparse sets (Q1177170) (← links)
- Separating complexity classes with tally oracles (Q1185002) (← links)
- Logarithmic advice classes (Q1193903) (← links)
- On sparse hard sets for counting classes (Q1210293) (← links)
- Almost-everywhere complexity hierarchies for nondeterministic time (Q1261465) (← links)
- Hard promise problems and nonuniform complexity (Q1261468) (← links)
- Strong nondeterministic Turing reduction - a technique for proving intractability (Q1262762) (← links)
- Probabilistic complexity classes and lowness (Q1263979) (← links)
- On reductions of NP sets to sparse sets (Q1329162) (← links)
- Locating \(P\)/poly optimally in the extended low hierarchy (Q1341715) (← links)
- Competing provers yield improved Karp-Lipton collapse results (Q1775885) (← links)
- The robustness of LWPP and WPP, with an application to graph reconstruction (Q2027204) (← links)
- Collapsing degrees via strong computation (Q2366690) (← links)
- The complexity of two problems on arithmetic circuits (Q2465637) (← links)
- Separating the low and high hierarchies by oracles (Q2638773) (← links)
- Reducibilities on tally and sparse sets (Q3357534) (← links)
- Characterizing polynomial complexity classes by reducibilities (Q3489449) (← links)
- On the complexity of graph reconstruction (Q4298372) (← links)
- Fault-tolerance and complexity (Extended abstract) (Q4630260) (← links)
- New collapse consequences of NP having small circuits (Q4645178) (← links)
- Complete sets and closeness to complexity classes (Q4727430) (← links)
- On closure properties of bounded two-sided error complexity classes (Q4835865) (← links)
- (Q5005153) (← links)
- Promise problems and access to unambiguous computation (Q5096827) (← links)
- Counting classes: Thresholds, parity, mods, and fewness (Q5905584) (← links)
- Dot operators (Q5958134) (← links)
