ARTICLE
Mayo98a1/IDIAP
On the Complexity of Recognizing Regions Computable by Two-Layered Perceptrons
Mayoraz, Eddy
EXTERNAL
http://publications.idiap.ch/attachments/reports/1998/rr98-03.pdf
PUBLIC
http://publications.idiap.ch/index.php/publications/showcite/mayo98a
Related documents
Annals Mathematics and Artificial Intelligence
1999
This work is concerned with the computational complexity of the recognition of $ÃžPtwo$, the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Some subclasses of $ÃžPtwo$ of particular interest are also studied, such as the class of iterated differences of polyhedra, or the class of regions $V$ that can be classified by a two-layered perceptron with as only hidden units the ones associated to $(d-1)$-dimensional facets of $V$. In this paper, we show that the recognition problem for $ÃžPtwo$ 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.
REPORT
Mayo98a/IDIAP
On the Complexity of Recognizing Regions Computable by Two-Layered Perceptrons
Mayoraz, Eddy
EXTERNAL
http://publications.idiap.ch/attachments/reports/1998/rr98-03.pdf
PUBLIC
Idiap-RR-03-1998
1998
IDIAP
This work is concerned with the computational complexity of the recognition of $ÃžPtwo$, the class of regions of the Euclidian space that can be classified exactly by a two-layered perceptron. Some subclasses of $ÃžPtwo$ of particular interest are also studied, such as the class of iterated differences of polyhedra, or the class of regions $V$ that can be classified by a two-layered perceptron with as only hidden units the ones associated to $(d-1)$-dimensional facets of $V$. In this paper, we show that the recognition problem for $ÃžPtwo$ 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.