13
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Could you please explain what "complex" means in your field? Does it mean, the neurons are firing meaningfully or more of them participating? $\endgroup$
    – v s
    Commented Feb 18, 2012 at 4:14
  • $\begingroup$ @v s: There are many competing definitions for "complex". Some say the most complex process is that with the highest entropy. That, however, would imply that random processes are complex, which doesn't seem biologically realistic. Even so, "firing meaningfully" is closer than "more ... participating" although likely "more participating meaningfully" is even closer. $\endgroup$
    – mac389
    Commented Feb 18, 2012 at 17:44
  • 1
    $\begingroup$ We understand complex implies larger entropy from our field. I asked that question to understand what your field means by complex. So " "more participating meaningfully" is closer. Ok. This is my guess. To me "more participating meaningfully" implies the neurons are communicating "intelligently" or "rather responding to stimuli" for a "particular desired outcome". This meaningful communication is usually associated with higher entropy or information in information theory. $\endgroup$
    – v s
    Commented Feb 18, 2012 at 18:21
  • $\begingroup$ @v s: There is a question of how two quantify entropy when the encoding scheme is not known and likely is switching, as seems to be the case in the brain. People have said used the mutual information between one neuron and a stimulus to quantify how selective that neuron is for that stimulus. The issue becomes more muddled when considering the more realistic case of many neurons. $\endgroup$
    – mac389
    Commented Feb 18, 2012 at 23:19
  • 1
    $\begingroup$ @mac389 we might mean any number of things as the complexity of an object. some examples are: Kolmogorov complexity (which you got an an answer) and various notions of time-bounded Kolmogorov complexity; when you have a family of objects of varying sizes, we look at how much time/space (as function of object size) does it take an algorithm to recognize that an object belongs to the class. you have a fairly non-trivial modeling problem here i think. $\endgroup$
    – Sasho Nikolov
    Commented Feb 18, 2012 at 23:42

4 Answers 4

Reset to default
10
$\begingroup$

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/

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, along with a discussion with more knowledgeable people this is exactly what I was looking for. $\endgroup$
    – mac389
    Commented Feb 18, 2012 at 17:48
8
$\begingroup$

Many people have mentioned Kolmogorov complexity or its resource-bounded variants, but I think something closer to what you're looking for is the notion of (logical) depth. There are several variants on depth, but they all try to get at something like what you're talking about. In particular, neither purely random strings nor very highly ordered/repetitive strings are deep.

One notion of depth is intuitively: a string is deep if it has a short description, but the only way to reconstruct the string from that short description takes an inordinate amount of time. This is the notion of depth and several others are introduced and developed in [1]. The other standard reference is [2]. I would look at those, then do a forward reference search.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, N. V. Vinodchandran. Computational depth: concept and applications. Theoret. Comp. Sci. 354(3):391--404. Also available freely from the author's webpage.

[2] C.H. Bennett. Logical depth and physical complexity. In R. Herken (Ed.), The Universal Turing Machine: A Half-Century Survey, Oxford University Press, Oxford (1988), 227–-257.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for this answer. Logical depth seems to be very close to what I meant by complexity. $\endgroup$
    – mac389
    Commented Feb 22, 2012 at 20:08
3
$\begingroup$

The first thing that comes to mind as something you might find fascinating is Kolmogorov complexity; I certainly find it fascinating, and since you didn't mention it, I thought it might be worth mentioning.

That being said, a more general approach to answering this question might be based on the theory of languages and automata. Deterministic finite automata are O(n) string processors. That is, given a string of length n, they process the string in precisely n steps (a lot of this depends on precisely how you define deterministic finite automata; however, a DFA certainly does not require more steps). Nondeterministc finite automata recognize the same languages (sets of strings) as DFAs, and can be transformed to DFAs, but to simulate an NFA on a sequential, deterministic machine, you must typically explore a tree-like "search space" which can increase the complexity dramatically. The regular languages are not very "complex" in a computational sense, since we can determine whether a string is in a particular regular language in time proportional to the length of the string.

You can similarly look at other levels of the Chomsky hierarchy of languages - deterministic context-free, context-free (including nondeterministic context free languages, which cannot necessarily be recognized by deterministic pushdown automata), the context-sensitive languages, the recursive and recursively enumerable languages, and the undecidable languages.

Different automata differ primarily in their external storage; i.e., what external storage is necessary for the automata to correctly process languages of a certain type. Finite automata have no external storage; PDAs have a stack, and Turing machines have a tape. You could thus interpret complexity of a particular programming problem (which corresponds to a language) to be related to the amount or kind of storage required to recognize it. If you need no or a fixed, finite amount of storage to recognize all strings in a language, it's a regular language. If all you need is a stack, you have a context-free language. Etc.

In general, I wouldn't be surprised if languages higher in the Chomsky hierarchy (hence with higher complexity) also tend to have higher entropy in the information-theoretic sense. That being said, you could probably find lots of counterexamples to this idea, and I have no idea whether there's any merit to it at all.

Also, this might be better asked at the "theoretical cs" (cstheory) StackExchange.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I did migrate it and thanks for your suggestion. $\endgroup$
    – mac389
    Commented Feb 18, 2012 at 17:45
1
$\begingroup$

Computational complexity addresses necessary resources: Given a particular type of problem, of some given size, what are the necessary resources (usually time, space, or both; and a particular type of computing device) to solve it. Problems are then grouped together in complexity "classes".

Some of these are rather general and abstract: Is the problem solvable at all, even in principle? Does it require a machine of this type, or that? The introduction to these ideas is still a graduate-level computer science topic, and the introduction material usually makes reference to the Chomsky hierarchy, which neatly (and beautifully!) maps together a few types of abstract machines, and a few types of abstract, mathematical language specifications.

Some of these, at the lower level, are more practical in every day use: Does this problem scale as the square of the problem size, or the cube, or some other function? Interestingly, I do know that arguments to the entropy of a given problem have been found useful in determining some lower bounds to some computational problems. One that sticks out in my mind (although I could probably not repeat it without checking a textbook) is an entropy-based argument for the minimum necessary number of comparisons during a sort. The connection to entropy is through information theory.

So there is some merit to the idea, I think.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.