logo Idiap Research Institute        
 [BibTeX] [Marc21]
On the Complexity of the Class of Regions Computable by a Two-Layered Perceptron
Type of publication: Idiap-RR
Citation: Mayo96a
Number: Idiap-RR-03-1996
Year: 1996
Institution: IDIAP
Abstract: 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.
Userfields: ipdmembership={learning},
Projects Idiap
Authors Mayoraz, Eddy
Added by: [UNK]
Total mark: 0
  • rr96-03.pdf
  • rr96-03.ps.gz