HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Síma, J. Articles by Sgall, J. Search for Related Content PubMed PubMed Citation Articles by Síma, J. Articles by Sgall, J.

On the Nonlearnability of a Single Spiking Neuron

Jií íma

sima{at}cs.cas.cz, Institute of Computer Science, Academy of Sciences of the Czech Republic, P.O. Box 5, 18207 Prague 8, Czech Republic

Jií Sgall

sgall{at}math.cas.cz, Mathematical Institute, Academy of Sciences of the Czech Republic, itná 25, 11567 Prague 1, Czech Republic

We study the computational complexity of training a single spiking neuron with binary coded inputs and output that, in addition to adaptive weights and a threshold, has adjustable synaptic delays. A synchronization technique is introduced so that the results concerning the nonlearnability of spiking neurons with binary delays are generalized to arbitrary real-valued delays. In particular, the consistency problem for with programmable weights, a threshold, and delays, and its approximation version are proven to be NP-complete. It follows that the spiking neurons with arbitrary synaptic delays are not properly PAC learnable and do not allow robust learning unless RP = NP. In addition, the representation problem for , a question whether an n-variable Boolean function given in DNF (or as a disjunction of O(n) threshold gates) can be computed by a spiking neuron, is shown to be coNP-hard.