On the Complexity of Learning Minimum Time-Bounded Turing Machines

DOI10.1137/0220059MaRDI QIDQ3357539zbMATH OpenOpenAlexFDO

Authors 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

feasible learning theorygeneralized Kolmogorov complexityNP-completeness

Mathematics Subject Classification ID

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

Recommendations

• On polynomial-time learnability in the limit of strictly deterministic automata
• Computability-theoretic learning complexity
• Resource restricted computability theoretic learning: Illustrative topics and problems
• Resource Restricted Computability Theoretic Learning: Illustrative Topics and Problems
• scientific article; zbMATH DE number 1281920
• Learning in a compiler for MINSAT algorithms
• On Optimal Learning Algorithms for Multiplicity Automata
• General lower bounds on the query complexity within the exact learning model
• Complexity theoretic limitations on learning halfspaces

Cited in

(20)

• An excursion to the Kolmogorov random strings
• Zero knowledge and circuit minimization
• 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
• The complexity of learning SUBSEQ(A)
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• Resource Restricted Computability Theoretic Learning: Illustrative Topics and Problems
• scientific article; zbMATH DE number 7754310 (Why is no real title available?)
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Capturing one-way functions via NP-hardness of meta-complexity
• A duality between one-way functions and average-case symmetry of information
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Gap MCSP is not (Levin) NP-complete in obfustopia
• NP-hardness of approximating meta-complexity: a cryptographic approach
• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: On the Complexity of Learning Minimum Time-Bounded Turing Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3357539)