Relation entre la complexité de calcul et l'information

Je travaille dans un laboratoire de neurosciences computationnelles qui quantifie les informations mutuelles entre paires ou groupes de neurones. Récemment, le patron s'est concentré sur la mesure de la "complexité de la dynamique neuronale". En poursuivant cette ligne de recherche, certaines personnes de mon groupe semblent assimiler "complexe" avec "a une forte entropie".

Quelqu'un peut-il me guider sur la relation entre la complexité de calcul (au sens CS) et l'entropie au sens de la théorie de l'information?

Pour expliquer un peu plus loin, des mesures comme la complexité de Lempel-Ziv, ne me semblent pas des mesures valides de complexité car elles confondent informatives (pour l'utilisateur) avec beaucoup de bits. D'autres mesures, comme celles-ci, [Causal State Splitting Reconstruction][1]sont beaucoup moins connues mais ont la propriété intéressante que les processus aléatoires ont une complexité nulle, car aucun état caché n'est nécessaire pour représenter un processus aléatoire stationnaire.

Il existe suffisamment de liens entre la théorie de l'information et la complexité informatique pour mériter un cours de deuxième cycle, par exemple celui-ci: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/

Beaucoup de gens ont mentionné la complexité de Kolmogorov ou ses variantes liées aux ressources, mais je pense que quelque chose de plus proche de ce que vous recherchez est la notion de profondeur (logique) . Il existe plusieurs variantes de profondeur, mais elles essaient toutes de parvenir à quelque chose comme ce dont vous parlez. En particulier, ni les chaînes purement aléatoires ni les chaînes très fortement ordonnées / répétitives ne sont profondes.

Une notion de profondeur est intuitivement: une chaîne est profonde si elle a une courte description, mais le seul moyen de reconstruire la chaîne à partir de cette courte description prend un temps excessif. C'est la notion de profondeur et plusieurs autres sont introduites et développées dans [1]. L'autre référence standard est [2]. Je les examinerais, puis ferais une recherche de références.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, NV Vinodchandran. Profondeur de calcul: concept et applications . Théorète. Comp. Sci. 354 (3): 391--404. Également disponible gratuitement sur la page Web de l'auteur .

[2] CH Bennett. Profondeur logique et complexité physique. Dans R. Herken (Ed.), The Universal Turing Machine: A Half-Century Survey, Oxford University Press, Oxford (1988), 227-257.

La première chose qui vous vient à l'esprit comme quelque chose que vous pourriez trouver fascinant est la complexité de Kolmogorov; Je le trouve certainement fascinant, et comme vous ne l'avez pas mentionné, j'ai pensé que cela valait la peine d'être mentionné.

Cela étant dit, une approche plus générale pour répondre à cette question pourrait être basée sur la théorie des langages et des automates. Les automates finis déterministes sont des processeurs de chaîne O (n). Autrement dit, étant donné une chaîne de longueur n, ils traitent la chaîne en n étapes précisément (cela dépend en grande partie de la façon dont vous définissez les automates finis déterministes; cependant, un DFA ne nécessite certainement pas plus d'étapes). Les automates finis non déterministes reconnaissent les mêmes langages (ensembles de chaînes) que les DFA et peuvent être transformés en DFA, mais pour simuler un NFA sur une machine séquentielle et déterministe, vous devez généralement explorer un "espace de recherche" en forme d'arbre qui peut augmenter la dramatiquement la complexité. Les langages réguliers ne sont pas très "complexes" au sens informatique,

Vous pouvez également regarder d'autres niveaux de la hiérarchie Chomsky des langues - sans contexte déterministe, sans contexte (y compris les langues sans contexte non déterministe, qui ne peuvent pas nécessairement être reconnues par les automates déterministes), les langues contextuelles, récursives et récursives les langues énumérables et les langues indécidables.

Les différents automates diffèrent principalement par leur stockage externe; c'est-à-dire, quel stockage externe est nécessaire pour que les automates traitent correctement les langages d'un certain type. Les automates finis n'ont pas de stockage externe; Les PDA ont une pile et les machines Turing ont une bande. Vous pourriez ainsi interpréter la complexité d'un problème de programmation particulier (qui correspond à un langage) comme étant liée à la quantité ou au type de stockage requis pour le reconnaître. Si vous n'avez besoin d'aucun stockage fixe ou limité pour reconnaître toutes les chaînes dans une langue, c'est une langue normale. Si vous n'avez besoin que d'une pile, vous disposez d'un langage sans contexte. Etc.

En général, je ne serais pas surpris si les langues plus élevées dans la hiérarchie de Chomsky (donc avec une complexité plus élevée) ont également tendance à avoir une entropie plus élevée au sens de la théorie de l'information. Cela étant dit, vous pourriez probablement trouver de nombreux contre-exemples à cette idée, et je ne sais pas du tout si elle est valable.

En outre, cela pourrait être mieux demandé au StackExchange "cs théorique" (cstheory).

La complexité informatique concerne les ressources nécessaires: étant donné un type particulier de problème, d'une certaine taille donnée, quelles sont les ressources nécessaires (généralement le temps, l'espace ou les deux; et un type particulier de dispositif informatique) pour le résoudre. Les problèmes sont ensuite regroupés en "classes" de complexité.

Certains d'entre eux sont plutôt généraux et abstraits: le problème est-il résoluble, même en principe? Faut-il une machine de ce type, ou ça? L'introduction à ces idées est toujours un sujet d'informatique de niveau universitaire, et le matériel d'introduction fait généralement référence à la hiérarchie Chomsky, qui mappe soigneusement (et magnifiquement!) Ensemble quelques types de machines abstraites et quelques types d'abstraits, spécifications du langage mathématique.

Certains d'entre eux, au niveau inférieur, sont plus pratiques dans l'utilisation quotidienne: ce problème est-il mis à l'échelle comme le carré de la taille du problème, ou le cube, ou une autre fonction? Fait intéressant, je sais que les arguments pour l'entropie d'un problème donné se sont révélés utiles pour déterminer des limites inférieures à certains problèmes de calcul. Celui qui me vient à l'esprit (même si je ne pourrais probablement pas le répéter sans consulter un manuel) est un argument basé sur l'entropie pour le nombre minimum de comparaisons nécessaires lors d'un tri. La connexion à l'entropie passe par la théorie de l'information.

Il y a donc un certain mérite à l'idée, je pense.