Pages that link to "Item:Q1821559"
From MaRDI portal
The following pages link to Sets with small generalized Kolmogorov complexity (Q1821559):
Displaying 22 items.
- Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity (Q290244) (← links)
- Robust machines accept easy sets (Q914369) (← links)
- Kolmogorov complexity and degrees of tally sets (Q916650) (← links)
- On the complexity of ranking (Q920620) (← links)
- On sets polynomially enumerable by iteration (Q1176233) (← links)
- Strong and robustly strong polynomial-time reducibilities to sparse sets (Q1177170) (← links)
- Separating complexity classes with tally oracles (Q1185002) (← links)
- Almost everywhere high nonuniform complexity (Q1190985) (← links)
- Circuit size relative to pseudorandom oracles (Q1208410) (← links)
- Locating \(P\)/poly optimally in the extended low hierarchy (Q1341715) (← links)
- Some consequences of the existnce of pseudorandom generators (Q1822961) (← links)
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets (Q1823690) (← links)
- NL-printable sets and nondeterministic Kolmogorov complexity (Q2369009) (← links)
- All superlinear inverse schemes are coNP-hard (Q2575753) (← links)
- Reducibilities on tally and sparse sets (Q3357534) (← links)
- Self-P-Printability and Polynomial Time Turing Equivalence to a Tally Set (Q3985806) (← links)
- New collapse consequences of NP having small circuits (Q4645178) (← links)
- Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ (Q4717047) (← links)
- A refinement of the low and high hierarchies (Q4841766) (← links)
- Upper bounds for the complexity of sparse and tally descriptions (Q4864446) (← links)
- Small Generating Sets and DLPC Problem (Q4976409) (← links)
- Degrees and reducibilities of easy tally sets (Q5096899) (← links)
