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.

Related material