DocumentCode :
3285768
Title :
Counting stable states and sizes of attraction domains in Hopfield nets is hard
Author :
Floreen, Patrik ; Orponen, Pekka
Author_Institution :
Dept. of Comput. Sci., Helsinki Univ., Finland
fYear :
1989
fDate :
0-0 1989
Firstpage :
395
Abstract :
It is shown that, given a Hopfield net, it is NP-hard to count either the number of stable states or the number of states converging to a given stable state. The latter result holds even when the interconnection weights between neurons are restricted to 0 or +or-1. The authors show that the stable state counting problem and the problem of counting states converging to a given stable state in a single parallel update step are both Hash P-complete. A remaining open problem is to show that computing the size of the full attraction domain of a given stable state is also Hash P-complete.<>
Keywords :
computational complexity; content-addressable storage; memory architecture; neural nets; Hash P-complete; Hopfield nets; NP-hard; associative memory network; attraction domains; computational complexity; content-addressable storage; memory architectures; neural nets; stable; Associative memories; Complexity theory; Memory architecture; Neural networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Neural Networks, 1989. IJCNN., International Joint Conference on
Conference_Location :
Washington, DC, USA
Type :
conf
DOI :
10.1109/IJCNN.1989.118614
Filename :
118614
Link To Document :
بازگشت