What is the relationship between the complexity and the fitness of evolved organisms, whether natural or artificial? It has been asserted, primarily based on empirical evidence, that the complexity of biological organisms increases as their fitness within a particular environment increases via evolution by natural selection. In this work, we derive an analytical expression for the minimal mutual information $I(\mathbf{s}:\mathbf{m})$ quantifying the organizational correlation between the sensory input $\mathbf{s}$ and the corresponding motor response $\mathbf{m}$ required for achieving a given fitness level $F$ in a given environment . We show that under certain conditions, the minimal mutual information $I(\mathbf{s}:\mathbf{m})$ is a semi-positive definite, monotonic non-decreasing, concave function of $F$.
We also simulated the adaptation of brains of digital organisms living in static mazes, whose {\it connectome} evolves over 10,000s of generations from a random initial state. We computed the circuit complexity of these brains as they evolve to adapt to their environment using an entropy-based measure known as {\it integrated information}. In a confirmation of our theoretical derivation, we find that the minimal complexity of the animats' brains increases with their fitness. That is, to achieve any given level of fitness, there exists a minimal amount of circuit complexity.
