Relation between different "complexity theories" and complex systems theory
For the relation between first and second look up descriptive complexity theory and finite model theory. This is a established branch of complexity theory and logic.