In this work, the authors consider a 2-layer, 3-node, n-input neural network whose nodes compute linear threshold functions of their inputs. They show that it is NP-complete to decide whether there exist weights and thresholds for this network so that it produces output consistent with a given set of training examples. They also extend the result to other simple networks. Furthermore, they also present a network for which training is hard but where switching to a more powerful representation makes training easier. These results suggest the importance, given a training problem, of finding an appropriate network and input encoding for that problem.