Part of Advances in Neural Information Processing Systems 9 (NIPS 1996)
Ian Parberry, Hung-Li Tseng
It is shown that conventional computers can be exponentiallx faster than planar Hopfield networks: although there are planar Hopfield networks that take exponential time to converge, a stable state of an arbitrary planar Hopfield network can be found by a conventional computer in polynomial time. The theory of 'P.cS-completeness gives strong evidence that such a separation is unlikely for nonpla(cid:173) nar Hopfield networks, and it is demonstrated that this is also the case for several restricted classes of nonplanar Hopfield networks, including those who interconnection graphs are the class of bipar(cid:173) tite graphs, graphs of degree 3, the dual of the knight's graph, the 8-neighbor mesh, the hypercube , the butterfly, the cube-connected cycles, and the shuffle-exchange graph.