On the power of neural networks for solving hard problems

AbstractThis paper deals with a neural network model in which each neuron performs a threshold logic function. An important property of the model is that it always converges to a stable state when operating in a serial mode. This property is the basis of the potential applications of the model such as associative memory devices and combinatorial optimization. One of the motivations for use of the model for solving hard combinatorial problems is the fact that it can be implemented by optical devices and thus operate at a higher speed than conventional electronics. The main theme in this work is to investigate the power of the model for solving NP-hard problems and to understand the relation between speed of operation and the size of a neural network. In particular, it will be shown that for any NP-hard problem the existence of a polynomial size network that solves it implies that NP = co-NP. Also, for the Traveling Salesman Problem (TSP), even a polynomial size network that gets an e-approximate solution does not exist unless P = NP. The above results are of great practical interest, because right now it is possible to build neural networks which will operate fast but are limited in the number of neurons they contain