Using Algorithmic Complexity Proxies in Disorders of Consciousness

Two EEG complexity measures that look different are actually the same algorithm applied to different experiments — and understanding that clarifies when to use each.

The core insight is simple: both resting EEG complexity (Lempel-Ziv complexity, or LZC) and the Perturbational Complexity Index (PCI) compress a binarized EEG signal and report how hard it is to compress. That's it. The algorithm is identical. What differs is which signal gets compressed: spontaneous brain activity in the resting case, versus the brain's response to a TMS "hammer blow" in the perturbational case. The paper's main contribution is making this equivalence precise using Kolmogorov complexity theory, then drawing the right clinical lesson from it.

A quick primer on what these measures actually estimate. True Kolmogorov complexity — the length of the shortest program that generates a given string — is uncomputable. LZ compression gives you a computable upper bound on it: the compressed file length is always at least as long as the theoretical minimum description, up to a fixed constant that depends on the compressor but not on the data. So when researchers report "LZ complexity" of an EEG signal, they're reporting how hard a specific compressor finds a specific encoding of that signal to compress. That's a real and useful quantity, but it's a property of the representation pipeline (filtering, binarization, channel selection) as much as of the brain.

Why does PCI outperform resting LZC in clinical practice, if they're computing the same thing? Experimental control, not algorithmic depth. Spontaneous EEG is noisy in the statistical sense: arousal fluctuates, patients drift toward sleep, medications alter spectral content, and none of this is the clinician's fault. A low resting complexity score might mean impaired consciousness, or it might mean the patient was drowsy during recording. TMS delivers a known perturbation at a known time to a known cortical location, bypassing sensory and motor pathways entirely. The complexity of the response to that controlled impulse is therefore a cleaner read on whether the cortex can still propagate a signal in a rich, differentiated way. The paper cites empirical cases where resting EEG looks impoverished (lots of slow delta, little alpha) while PCI remains in the "conscious" range — patients who appear vegetative by behavior but whose cortex still responds complexly when prodded. This dissociation is expected under the framework: low arousal can suppress the expression of complex dynamics at rest without destroying the cortex's capacity to generate them.

The clinical takeaway is a combination strategy, not a competition. Resting LZC is cheap, passive, scalable, and good for screening and longitudinal tracking. PCI requires TMS hardware and expert artifact handling, but it's the right tool when behavior is absent or the resting record is ambiguous. The paper argues this division of labor follows directly from the algorithmic analysis — not from one measure being "deeper" than the other, but from one having better experimental control over its input.