REPORT Mayo96a/IDIAP On the Complexity of the Class of Regions Computable by a Two-Layered Perceptron Mayoraz, Eddy EXTERNAL http://publications.idiap.ch/attachments/reports/1996/rr96-03.pdf PUBLIC Idiap-RR-03-1996 1996 IDIAP 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.