On the complexity of small description and related topics

DOI10.1007/3-540-55808-X_8zbMath1493.68154OpenAlexW1514031921MaRDI QIDQ5096821

Osamu Watanabe

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55808-x_8

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Locating \(P\)/poly optimally in the extended low hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Continuous optimization problems and a polynomial hierarchy of real functions
• Learning regular sets from queries and counterexamples
• When won't membership queries help?
• Queries and concept learning
• A theory of the learnable
• Complexity Measures for Public-Key Cryptosystems
• On the Computational Complexity of Small Descriptions
• A framework for polynomial-time query learnability
• Structural analysis of polynomial-time query learnability
• Cryptographic limitations on learning Boolean formulae and finite automata

This page was built for publication: On the complexity of small description and related topics