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. Some subclasses of of particular interest are also studied, such as the class of iterated differences of polyhedra, or the class of regions that can be classified by a two-layered perceptron with as only hidden units the ones associated to -dimensional facets of . In this paper, we show that the recognition problem for as well as most other subclasses considered here is \NPH\ in the most general case. We then identify special cases that admit polynomial time algorithms.
Frédéric Kaplan, Maud Ehrmann, Matteo Romanello, Sven-Nicolas Yoann Najem, Emanuela Boros
David Atienza Alonso, Tomas Teijeiro Campo, Una Pale
Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen