NeuroCOLT

Neural Networks and Computational Learning Theory

About NeuroCOLT

Papers Archive

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-96-020

Characterizing the Learnability of Kolmogorov Easy Circuit Expressions

Josè L. Balcazar
Universitat Politecnica de Catalunya
Spain

Harry Buhrman
Centrum voor Wiskunde en Informatica
The Netherlands

Abstract
We show that Kolmogorov easy circuit expressions can be learned with membership queries in polynomial time if and only if every NE-predicate is E-solvable. Moreover we show that the previously known algorithm, that uses an oracle in NP, is optimal in some relativized world.

Download Compressed Postscript