On the complexity of consistency problems for neurons with binary weights
FakultätenFakultät für Ingenieurwissenschaften und Informatik
We inquire into the complexity of training a neuron with binary weights when the training examples are Boolean and required to have bounded coincidence and heaviness. Coincidence of an example set is defined as the maximum inner product of two elements, heaviness of an example set is the maximum Hamming-weight of an element. We use both as parameters to define classes of restricted consistency problems and ask for which values they are NP-complete or solvable in polynomial time.
Erstellung / Fertigstellung
Normierte SchlagwörterNeuronales Netz [GND]
Neural networks (Computer science) [LCSH]
NP-complete problems [LCSH]