Classifying neural networks

Certain aspects of the classification of discrete synchronous neural networks are examined. Neural networks with different weights and thresholds may give rise to the same dynamics digraphs. These networks are said to be isomorphic. Testing the isomorphism of dynamics digraphs results in two different classes of digraphs: labeled or unlabeled. The corresponding decision problems are called strong-isomorphism testing (SIT) and weak-isomorphism testing (WIT). Several results which show that the nature of these problems is in contrast with that of the graph-isomorphism problem are proven. For instance, SIT is coNP-complete, and WIT is NP-hard (even for symmetric networks) despite several structural restrictions of the digraphs under consideration. The reductions also show that predecessor counting is #P-complete