Structural complexity and neural networks

We survey some relationships between computational complexity and neural network theory. Here, only networks of binary threshold neurons are considered. We begin by presenting some contributions of neural networks in structural complexity theory. In parallel complexity, the class TC0 k of problems solvable by feed-forward networks with k levels and a polynomial number of neurons is considered. Separation results are recalled and the relation between TC0 =∪TC0 k and NC1 is analyzed. In particular, under the conjecture TC ≠ NC1, we characterize the class of regular languages accepted by feed-forward networks with a constant number of levels and a polynomial number of neurons. We also discuss the use of complexity theory to study computational aspects of learning and combinatorial optimization in the context of neural networks. We consider the PAC model of learning, emphasizing some negative results based on complexity theoretic assumptions. Finally, we discussed some results in the realm of neural networks related to a probabilistic characterization of NP.