Complexity is the number of strong connections.

In the human nervous system, Eagleman (2015) explains:

The connections between neurons are called synapses. These connections are where chemicals called neurotransmitters carry signals between neurons. But synaptic connections are not all of the same strength: depending on their history of activity, they can become stronger or weaker. As synapses change their potency, information flows through the network differently. If a connection gets weak enough, it whithers and goes away. If it gets strengthened, it can sprout new connections. (Kindle location 1175)

Kandel (1989), a Nobel-prize winning neuroscientist, concluded from empirical evidence that:

Learning produces changes in neuronal architecture (p. 103)…. Whereas short-term memory does not require the synthesis of new proteins … the consolidation of long-term memory … does require new protein synthesis (p. 109). … [T]he long-term process differs from the short-term process in two important ways:  one, the long-term process requires translation and transcription, and two, the long-term process is associated with growth in synaptic connections (p. 115, bolding added) …. Our evidence suggests that learning produces enduring changes in the structure and function of synapses... (p. 121, bolding added)

For a recent overview of complexity of mental structures, see Bertolero & Bassett (2019): How the mind emerges from the brain's complex networks, in Scientific American.

How does this reconcile with the fact that as humans develop and learn, the structure of the nervous system is pruned? Eagleman (2015) writes:

As you mature, 50% of your synapses will be pared back. Which synapses stay and which go? When a synapse successfully participates in a circuit, it is strengthened; in contrast, synapses weaken if they aren't useful, and eventually they are eliminated. Just like paths in a forest, you lose the connections you don't use.... Our brains form fewer but stronger connections. (Kindle location 122)

While the overall complexity of the nervous system structure may decrease, the number of strong connections increases as humans learn. Stronger connections are more likely to fire, i.e., to send neurotransmitters to other connected neurons. Strength of a connection is related to its biochemistry.

Note: In Axiomatic Theories of Intentional Systems (ATIS: Thompson, 2006a; 2006b; 2008a; 2008b), complexity refers to the number of affect-relations, which are connections among components of a system. See the ATIS Glossary. The definition of complexity here refers to the number of biochemically strong connections. In ATIS Graph Theory, the strength of a connection is indicated by its weight. "Affect-relation weight is ... the weight or value associated with an affect-relation (Thompson, 2008b, p. 24).