Sets with small generalized Kolmogorov complexity
From MaRDI portal
Publication:1821559
DOI10.1007/BF00264313zbMath0616.68046MaRDI QIDQ1821559
José L. Balcázar, Ronald V. Book
Publication date: 1986
Published in: Acta Informatica (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
Related Items
Complexity classes between $\Theta _k^P$ and $\Delta _k^P$, A refinement of the low and high hierarchies, Upper bounds for the complexity of sparse and tally descriptions, 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, Circuit size relative to pseudorandom oracles, Locating \(P\)/poly optimally in the extended low hierarchy