On the complexity of training perceptrons