Some results on the computational complexity of symmetric connectionist networks

Connectionists models are currently being investigated actively by many researchers in artificial intelligence, information theory and computational neuroscience. These networks have been shown to be applicable to a wide range of domains such as content addressable memories, semantic nets, computer vision, natural language parsing, speech recognition, and approximation schemes for difficult optimization problems. In this paper, we address several basic problems related to the computational complexity of discrete Hopfield nets (connectionist networks with symmetric connections).This research was supported in part by AFOSR Grant No. AFOSR-89-1151 and NSF Grant No. IRI-88-09324.