Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problems

Modern Hopfield Networks (MHNs) have emerged as powerful components in deep learning, serving as effective replacements for pooling layers, LSTMs, and attention mechanisms. While recent advancements have significantly improved their storage capacity and retrieval efficiency, their fundamental theoretical boundaries remain underexplored. In this paper, we rigorously characterize the expressive power of MHNs through the lens of circuit complexity theory. We prove that poly(n)-precision MHNs with constant depth and linear hidden dimension fall within the mathsfDLOGTIME-uniform mathsfTC0 complexity class. Consequently, assuming mathsfTC0 neq mathsfNC1, we demonstrate that these architectures are incapable of solving mathsfNC1-hard problems, such as undirected graph connectivity and tree isomorphism. We further extend these impossibility results to Kernelized Hopfield Networks. However, we show that these limitations are not absolute: we prove that equipping MHNs with a Chain-of-Thought (CoT) mechanism enables them to transcend the mathsfTC0 barrier, allowing them to solve inherently serial problems like the word problem for the permutation group S5. Collectively, our results delineate a fine-grained boundary between the capabilities of standard MHNs and those augmented with reasoning steps.