On the Complexity of Training a Single Perceptron with Programmable Synaptic Delays

Abstract

We consider a single perceptron $\mathcal{N}$ with synaptic delays which generalizes a simplified model for a spiking neuron where not only the time that a pulse needs to travel through a synapse is taken into account but also the input firing rates may have more different levels. A synchronization technique is introduced so that the results concerning the learnability of spiking neurons with binary delays also apply to $\mathcal{N}$ with arbitrary delays. In particular, the consistency problem for $\mathcal{N}$ with programmable delays and its approximation version prove to be NP-hard. It follows that the perceptrons with programmable synaptic delays are not properly PAC-learnable and the spiking neurons with arbitrary delays do not allow robust learning unless RP = NP . In addition, we show that the representation problem for $\mathcal{N}$ which is an issue 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 co-NP-hard.