Publication
This work is concerned with the computational complexity of the recognition of , the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Several subclasses of of particular interest are also considered. We show that the recognition problems of and of other classes considered here are intractable, even in some favorable circumstances. We then identify special cases having polynomial time algorithms.
Frédéric Kaplan, Maud Ehrmann, Matteo Romanello, Sven-Nicolas Yoann Najem, Emanuela Boros
Michael Herzog, Christian Sachse, Adrien Christophe Doerig
Florian Frédéric Vincent Breider, Myriam Borgatta