Relation between computational complexity and information I work in a computational neuroscience lab that quantifies the mutual information between pairs or groups of neurons. Recently, the boss his shifted focus to measuring the "complexity of neural dynamics". In pursuing that line of research, some people in my group appear to equate "complex" with "has a high entropy". 

Can anybody guide me on what the relationship is between computational complexity (in a CS sense) and entropy in the information theory sense?

To explain a bit further, measures like Lempel-Ziv complexity, don't seem, to me, valid measures of complexity because they conflate informative (to the user) with carrying a lot of bits. Other measures, like [Causal State Splitting Reconstruction][1] are much less known but have the appealing property that random processes have zero complexity, because zero hidden states are needed to represent a stationary random process.
There are enough connections between information theory and computational complexity to merit a graduate course, e.g. this one: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/