Computational complexity theory classifies problems according to their inherent difficulty.
Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the properties of the system's individual parts. Examples include chaotic systems, complex adaptive systems, or nonlinear systems.
Is there any formal bridge between these fields?
For what it's worth, the notion of performing cryptography with cellular automata is not new, and earlier this year Applebaum, Ishai, and Kushilevitz identified "complexity" with computational intractability.