On the Complexity of Learning Minimum Time-Bounded Turing Machines

DOI10.1137/0220059zbMath0731.68048OpenAlexW2086059606MaRDI QIDQ3357539

Ker-I. Ko

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220059

zbMATH Keywords

NP-completenessgeneralized Kolmogorov complexityfeasible learning theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

An excursion to the Kolmogorov random strings ⋮ Zero knowledge and circuit minimization ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Unnamed Item ⋮ Unnamed Item