The social brain hypothesis proposes that enlarged brains have evolved in response to the increasing cognitive demands that complex social life in larger groups places on primates and other mammals. However, this reasoning can be challenged by evidence that brain size has decreased in the evolutionary transitions from solitary to social larger groups in the case of Neolithic humans and some eusocial insects. Different hypotheses can be identified in the literature to explain this reduction in brain size. We evaluate some of them from the perspective of recent approaches to cognitive science, which support the idea that the basis of cognition can span over brain, body, and environment. Here we show through a minimal cognitive model using an evolutionary robotics methodology that the neural complexity, in terms of neural entropy and degrees of freedom of neural activity, of smaller-brained agents evolved in social interaction is comparable to the neural complexity of larger-brained agents evolved in solitary conditions. The nonlinear time series analysis of agents’ neural activity reveals that the decoupled smaller neural network is intrinsically lower dimensional than the decoupled larger neural network. However, when smaller-brained agents are interacting, their actual neural complexity goes beyond its intrinsic limits achieving results comparable to those obtained by larger-brained solitary agents. This suggests that the smaller-brained agents are able to enhance their neural complexity through social interaction, thereby offsetting the reduced brain size.