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


Eddy Mayoraz


Abstract:

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