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 contributions in structural In parallel complexity, the class TCk0 problems solvable feed-forward with k levels a polynomial number is considered. Separation results recalled relation TC0 = ?TCk0 NC1 analyzed. particular, under conjecture TC ? NC1, we characterize regular languages accepted constant neurons.We also discuss use theory to study aspects learning combinatorial optimization context networks. consider PAC model learning, emphasizing negative based on theoretic assumptions. Finally, discussed realm related probabilistic characterization NP.