The difficulty of reduced error pruning of leveled branching programs

DOI10.1023/B:AMAI.0000018579.44321.6AzbMath1062.68096OpenAlexW2038922054MaRDI QIDQ596496

Matti Kääriäinen, Tapio Elomaa

Publication date: 10 August 2004

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/b:amai.0000018579.44321.6a

zbMATH Keywords

NP-completenessconcept learningbranching programsapproximabilityreduced error pruning

Mathematics Subject Classification ID

Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor

This page was built for publication: The difficulty of reduced error pruning of leveled branching programs