Title: Intrinsic Computational Complexity of Equivariant Neural Networks. Abstract: Equivariant neural networks have shown significant advantages in learning on data with intrinsic symmetries represented by groups. A major concern is on the high computational costs in the cases of large-scale groups, especially in the inference stage. This paper studies the required computational complexity of equivariant neural networks in inference for achieving a desired expressivity. We theoretically compare three classes of ReLU networks: (1) two-layer group-averaging networks (TGNs); (2) two-layer layer-wise equivariant networks (TENs); and (3) two-layer networks without any equivariant constraints (TNs), with a new notion {\it intrinsic computational complexity} for better characterizing computational costs. We prove that (1) TGNs/TENs have equal and full expressivities to represent any invariant function that can be learned by a TN, where the TGNs and TENs have equal intrinsic computational complexities; (2) a TGN/TEN requires at most double the intrinsic computational complexity of a TN; and (3) a TEN can achieve the inference speed coincident with its intrinsic computational complexity, while TGNs are strictly slower, which justifies the computational advantages of layer-wise equivariant architectures over group averaging. Our theory rules out the existence of equivariant networks with group-scale-independent computational costs, summarized in a new no-free-lunch theorem: when more equivariance is desired, more computation is required.