Sets with small generalized Kolmogorov complexity
From MaRDI portal
Publication:1821559
DOI10.1007/BF00264313zbMath0616.68046OpenAlexW2061746118MaRDI QIDQ1821559
Ronald V. Book, José L. Balcázar
Publication date: 1986
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00264313
Related Items (18)
Locating \(P\)/poly optimally in the extended low hierarchy ⋮ A refinement of the low and high hierarchies ⋮ Degrees and reducibilities of easy tally sets ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Robust machines accept easy sets ⋮ Kolmogorov complexity and degrees of tally sets ⋮ On the complexity of ranking ⋮ On sets polynomially enumerable by iteration ⋮ Strong and robustly strong polynomial-time reducibilities to sparse sets ⋮ Separating complexity classes with tally oracles ⋮ Almost everywhere high nonuniform complexity ⋮ New collapse consequences of NP having small circuits ⋮ Circuit size relative to pseudorandom oracles ⋮ Reducibilities on tally and sparse sets ⋮ Complexity classes between $\Theta _k^P$ and $\Delta _k^P$ ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Distinguishing conjunctive and disjunctive reducibilities by sparse sets ⋮ All superlinear inverse schemes are coNP-hard
Cites Work
- Unnamed Item
- Unnamed Item
- A low and a high hierarchy within NP
- Complexity and structure
- On bounded query machines
- Continuous optimization problems and a polynomial hierarchy of real functions
- Curiouser and Curiouser: The Link between Incompressibility and Complexity
- Positive Relativizations of Complexity Classes
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On Restricting the Size of Oracles Compared with Restricting Access to Oracles
- Quantitative Relativizations of Complexity Classes
- A Theory of Program Size Formally Identical to Information Theory
- Information-Theoretic Limitations of Formal Systems
- On the Length of Programs for Computing Finite Binary Sequences
This page was built for publication: Sets with small generalized Kolmogorov complexity
