Resource demands of an implementationist approach to cognition

A core inferential problem in the study of natural and artificial systems is the following: given access to a neural network, a stimulus and behaviour of interest, and a method of systematic experimentation, figure out which circuit suffices to generate the behaviour in response to the stimulus. It is often assumed that the main obstacles to this "circuit cracking'' are incomplete maps (e.g., connectomes), observability and perturbability. Here we show through complexity-theoretic proofs that even if all these and many other obstacles are removed, an intrinsic and irreducible computational hardness remains. While this may seem to leave open the possibility that the researcher may in practice resort to approximation, we prove the task is inapproximable. We discuss the implications of these findings for implementationist versus functionalist debates on how to approach the study of cognitive systems.