Infoscience

Report

# On the Complexity of the Class of Regions Computable by a Two-Layered Perceptron

This work is concerned with the computational complexity of the recognition of $\mbox{LP}_2$, the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Several subclasses of $\mbox{LP}_2$ of particular interest are also considered. We show that the recognition problems of $\mbox{LP}_2$ and of other classes considered here are intractable, even in some favorable circumstances. We then identify special cases having polynomial time algorithms.

Keywords: neuron ; learning ; eddy

#### Reference

• EPFL-REPORT-82345

Record created on 2006-03-10, modified on 2017-05-10