Beziehung zwischen Rechenkomplexität und Information

Ich arbeite in einem rechnergestützten neurowissenschaftlichen Labor, das die gegenseitige Information zwischen Paaren oder Gruppen von Neuronen quantifiziert. Vor kurzem verlagerte der Chef seinen Fokus auf die Messung der "Komplexität der neuronalen Dynamik". Bei der Verfolgung dieser Forschungsrichtung scheinen einige Leute in meiner Gruppe "komplex" mit "hat eine hohe Entropie" gleichzusetzen.

Kann mich jemand anleiten, wie die Beziehung zwischen rechnerischer Komplexität (im Sinne von CS) und Entropie im Sinne der Informationstheorie aussieht?

Um es etwas näher zu erläutern: Maßnahmen wie die Komplexität von Lempel-Ziv scheinen mir keine gültigen Maßstäbe für die Komplexität zu sein, da sie informativ (für den Benutzer) mit dem Tragen vieler Bits in Verbindung stehen. Andere Maßnahmen wie [Causal State Splitting Reconstruction][1]sind viel weniger bekannt, haben jedoch die ansprechende Eigenschaft, dass zufällige Prozesse keine Komplexität aufweisen, da keine versteckten Zustände erforderlich sind, um einen stationären zufälligen Prozess darzustellen.

Es gibt genügend Verbindungen zwischen Informationstheorie und rechnerischer Komplexität, um einen Abschlusskurs zu verdienen, z. B. diesen: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/

Viele Leute haben Kolmogorovs Komplexität oder seine ressourcengebundenen Varianten erwähnt, aber ich denke, etwas näher an dem, was Sie suchen, ist der Begriff der (logischen) Tiefe . Es gibt verschiedene Varianten der Tiefe, aber alle versuchen, so etwas wie das zu erreichen, wovon Sie sprechen. Insbesondere sind weder rein zufällige Zeichenfolgen noch sehr hochgeordnete / sich wiederholende Zeichenfolgen tief.

Ein Begriff von Tiefe ist intuitiv: Eine Zeichenfolge ist tief, wenn sie eine kurze Beschreibung enthält, aber die einzige Möglichkeit, die Zeichenfolge aus dieser kurzen Beschreibung zu rekonstruieren, dauert übermäßig lange. Dies ist der Begriff der Tiefe, und mehrere andere werden in [1] eingeführt und weiterentwickelt. Die andere Standardreferenz ist [2]. Ich würde mir diese ansehen und dann eine Vorwärtsreferenzsuche durchführen.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, NV Vinodchandran. Computertiefe: Konzept und Anwendungen . Theoret. Comp. Sci. 354 (3): 391–404. Auch frei verfügbar auf der Webseite des Autors .

[2] CH Bennett. Logische Tiefe und physikalische Komplexität. In R. Herken (Hrsg.), The Universal Turing Machine: Eine Umfrage über ein halbes Jahrhundert, Oxford University Press, Oxford (1988), 227–257.

Das erste, was Ihnen als faszinierend in den Sinn kommt, ist die Komplexität von Kolmogorov. Ich finde es auf jeden Fall faszinierend, und da Sie es nicht erwähnt haben, dachte ich, es könnte erwähnenswert sein.

Ein allgemeinerer Ansatz zur Beantwortung dieser Frage könnte jedoch auf der Theorie der Sprachen und Automaten beruhen. Deterministische endliche Automaten sind O (n) String-Prozessoren. Das heißt, bei einer Zeichenfolge mit der Länge n verarbeiten sie die Zeichenfolge in genau n Schritten (vieles davon hängt davon ab, wie Sie deterministische endliche Automaten definieren; ein DFA erfordert jedoch sicherlich keine weiteren Schritte). Nichtdeterministische endliche Automaten erkennen dieselben Sprachen (Sätze von Zeichenfolgen) wie DFAs und können in DFAs transformiert werden. Um jedoch eine NFA auf einer sequentiellen, deterministischen Maschine zu simulieren, müssen Sie normalerweise einen baumartigen "Suchraum" untersuchen, der die Größe erhöhen kann Komplexität dramatisch. Die regulären Sprachen sind im rechnerischen Sinne nicht sehr "komplex".

Sie können auch andere Ebenen der Chomsky-Hierarchie von Sprachen betrachten - deterministisch kontextfrei, kontextfrei (einschließlich nichtdeterministischer kontextfreier Sprachen, die von deterministischen Pushdown-Automaten nicht unbedingt erkannt werden können), die kontextsensitiven Sprachen, die rekursiven und rekursiven Aufzählbare Sprachen und die unentscheidbaren Sprachen.

Verschiedene Automaten unterscheiden sich hauptsächlich in ihrem externen Speicher. dh welcher externe Speicher ist erforderlich, damit die Automaten Sprachen eines bestimmten Typs korrekt verarbeiten können. Endliche Automaten haben keinen externen Speicher; PDAs haben einen Stapel und Turing-Maschinen haben ein Band. Sie können also die Komplexität eines bestimmten Programmierproblems (das einer Sprache entspricht) so interpretieren, dass es mit der Menge oder Art des Speichers zusammenhängt, der erforderlich ist, um es zu erkennen. Wenn Sie keinen oder einen festen, begrenzten Speicherplatz benötigen, um alle Zeichenfolgen in einer Sprache zu erkennen, handelt es sich um eine reguläre Sprache. Wenn Sie nur einen Stapel benötigen, haben Sie eine kontextfreie Sprache. Usw.

Im Allgemeinen wäre ich nicht überrascht, wenn Sprachen, die in der Chomsky-Hierarchie höher sind (daher eine höhere Komplexität aufweisen), auch tendenziell eine höhere Entropie im informationstheoretischen Sinne aufweisen. Davon abgesehen könnten Sie wahrscheinlich viele Gegenbeispiele zu dieser Idee finden, und ich habe keine Ahnung, ob es überhaupt einen Wert dafür gibt.

Dies könnte auch besser beim "theoretischen cs" (cstheory) StackExchange gefragt werden.

Die Komplexität der Berechnungen befasst sich mit den erforderlichen Ressourcen: Welche Ressourcen (normalerweise Zeit, Raum oder beides und eine bestimmte Art von Computergerät) sind bei einem bestimmten Problemtyp und einer bestimmten Größe erforderlich, um das Problem zu lösen? Die Probleme werden dann in Komplexitätsklassen zusammengefasst.

Einige davon sind eher allgemein und abstrakt: Ist das Problem überhaupt prinzipiell lösbar? Benötigt es eine Maschine dieses oder jenes Typs? Die Einführung in diese Ideen ist immer noch ein Thema der Informatik für Hochschulabsolventen, und das Einführungsmaterial bezieht sich normalerweise auf die Chomsky-Hierarchie, die einige Arten von abstrakten Maschinen und einige Arten von abstrakten Maschinen sauber (und wunderschön!) Zusammenfasst. mathematische Sprachspezifikationen.

Einige davon auf der unteren Ebene sind im täglichen Gebrauch praktischer: Skaliert dieses Problem als Quadrat der Problemgröße, des Würfels oder einer anderen Funktion? Interessanterweise weiß ich, dass Argumente für die Entropie eines bestimmten Problems nützlich sind, um einige Untergrenzen für einige Rechenprobleme zu bestimmen. Eines, das mir in den Sinn kommt (obwohl ich es wahrscheinlich nicht wiederholen könnte, ohne ein Lehrbuch zu überprüfen), ist ein entropiebasiertes Argument für die minimal erforderliche Anzahl von Vergleichen während einer Sortierung. Die Verbindung zur Entropie erfolgt durch Informationstheorie.

Ich denke, die Idee hat einen gewissen Wert.