Związek między złożonością obliczeniową a informacją

Pracuję w obliczeniowym laboratorium neuronauki, które ocenia ilościowo wzajemną informację między parami lub grupami neuronów. Ostatnio szef skupił się na pomiarze „złożoności dynamiki neuronowej”. Prowadząc tę ​​linię badań, niektórzy ludzie w mojej grupie wydają się utożsamiać „kompleks” z „ma wysoką entropię”.

Czy ktoś może wskazać mi związek między złożonością obliczeniową (w sensie CS) a entropią w sensie teorii informacji?

Aby wyjaśnić nieco dalej, miary takie jak złożoność Lempela-Ziva nie wydają mi się miarodajnymi miarami złożoności, ponieważ łączą informacje (dla użytkownika) z przenoszeniem dużej ilości bitów. Inne miary, podobnie jak, [Causal State Splitting Reconstruction][1]są znacznie mniej znane, ale mają atrakcyjną właściwość, że procesy losowe mają zerową złożoność, ponieważ zero stanów ukrytych jest potrzebnych do reprezentowania stacjonarnego procesu losowego.

Istnieje wystarczająca liczba powiązań między teorią informacji a złożonością obliczeniową, aby zasłużyć na kurs dla absolwentów, np. Ten: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/

Wiele osób wspomniało o złożoności Kołmogorowa lub jego ograniczonych zasobach wariantach, ale myślę, że coś bliższego temu, czego szukasz, jest pojęcie (logicznej) głębi . Istnieje kilka wariantów głębokości, ale wszystkie próbują uzyskać coś takiego, o czym mówisz. W szczególności ani czysto losowe ciągi, ani bardzo wysoce uporządkowane / powtarzalne ciągi nie są głębokie.

Jedno pojęcie głębokości jest intuicyjne: łańcuch jest głęboki, jeśli ma krótki opis, ale jedyny sposób na odtworzenie łańcucha na podstawie tego krótkiego opisu zajmuje nadmiernie dużo czasu. Jest to pojęcie głębi, a kilka innych zostało wprowadzonych i rozwiniętych w [1]. Drugim standardowym odniesieniem jest [2]. Spojrzałbym na te, a następnie przeszukałem referencje.

[1] L. Antunes, L. Fortnow, D. van Melkebeek, NV Vinodchandran. Głębokość obliczeniowa: koncepcja i zastosowania . Teoretyczna Komp. Sci. 354 (3): 391--404. Dostępne również bezpłatnie ze strony autora .

[2] CH Bennett. Logiczna głębia i złożoność fizyczna. W R. Herken (red.), The Universal Turing Machine: A Half-Century Survey, Oxford University Press, Oxford (1988), 227–257.

Pierwszą rzeczą, która wydaje się fascynująca, jest złożoność Kołmogorowa; Z pewnością uważam to za fascynujące, a skoro o tym nie wspomniałeś, pomyślałem, że warto o tym wspomnieć.

To powiedziawszy, bardziej ogólne podejście do odpowiedzi na to pytanie może opierać się na teorii języków i automatów. Deterministyczne automaty skończone są procesorami łańcuchowymi O (n). To znaczy, biorąc pod uwagę ciąg o długości n, przetwarzają go dokładnie w krokach n (wiele z tego zależy od tego, jak dokładnie zdefiniujesz deterministyczne automaty skończone; jednak DFA z pewnością nie wymaga więcej kroków). Automaty skończone niedeterministyczne rozpoznają te same języki (zestawy ciągów) co DFA i mogą być przekształcane w DFA, ale aby symulować NFA na sekwencyjnej, deterministycznej maszynie, musisz zazwyczaj eksplorować drzewiastą „przestrzeń wyszukiwania”, która może zwiększyć złożoność dramatycznie. Zwykłe języki nie są zbyt „złożone” w sensie obliczeniowym,

Możesz podobnie spojrzeć na inne poziomy hierarchii języków Chomsky'ego - deterministyczne kontekstowe, bezkontekstowe (w tym niedeterministyczne języki kontekstowe, które niekoniecznie mogą być rozpoznane przez deterministyczne automaty wypychające), języki kontekstowe, rekurencyjne i rekurencyjne języki wyliczalne i nierozstrzygalne.

Różne automaty różnią się przede wszystkim pamięcią zewnętrzną; tzn. jaka pamięć zewnętrzna jest niezbędna, aby automaty poprawnie przetwarzały języki określonego typu. Automaty skończone nie mają pamięci zewnętrznej; Urządzenia PDA mają stos, a maszyny Turinga mają taśmę. W ten sposób można zinterpretować złożoność konkretnego problemu programistycznego (odpowiadającego językowi), aby był powiązany z ilością lub rodzajem pamięci wymaganej do jego rozpoznania. Jeśli nie potrzebujesz żadnej lub określonej, skończonej ilości miejsca do rozpoznania wszystkich ciągów w języku, jest to zwykły język. Jeśli wszystko, czego potrzebujesz, to stos, masz język bezkontekstowy. Itp.

Zasadniczo nie zdziwiłbym się, gdyby języki wyższe w hierarchii Chomsky'ego (stąd o większej złożoności) również miałyby wyższą entropię w sensie teoretycznym. To powiedziawszy, prawdopodobnie można znaleźć wiele kontrprzykładów dla tego pomysłu, a ja nie mam pojęcia, czy ma to jakąkolwiek wartość.

Można to również lepiej zadać na „teoretycznej cs” (cstheory) StackExchange.

Złożoność obliczeniowa odnosi się do niezbędnych zasobów: Biorąc pod uwagę konkretny typ problemu, o danym rozmiarze, jakie zasoby są niezbędne (zwykle czas, przestrzeń lub jedno i drugie oraz określony typ urządzenia komputerowego), aby go rozwiązać. Problemy są następnie grupowane w „klasy” złożoności.

Niektóre z nich są raczej ogólne i abstrakcyjne: czy problem w ogóle można rozwiązać, nawet w zasadzie? Czy wymaga maszyny tego typu, czy tamtejszej? Wprowadzenie do tych pomysłów jest nadal tematem informatyki na poziomie magisterskim, a materiał wprowadzający zwykle nawiązuje do hierarchii Chomsky'ego, która starannie (i pięknie!) Odwzorowuje kilka rodzajów abstrakcyjnych maszyn i kilka rodzajów abstrakcyjnych, specyfikacje języka matematycznego.

Niektóre z nich, na niższym poziomie, są bardziej praktyczne w codziennym użytkowaniu: Czy ten problem skaluje się jako kwadrat wielkości problemu, kostki lub innej funkcji? Co ciekawe, wiem, że argumenty za entropią danego problemu okazały się przydatne w określaniu niektórych dolnych granic niektórych problemów obliczeniowych. Ten, który pojawia się w moim umyśle (chociaż prawdopodobnie nie mógłbym go powtórzyć bez sprawdzenia podręcznika), jest argumentem opartym na entropii dla minimalnej niezbędnej liczby porównań podczas sortowania. Połączenie z entropią odbywa się poprzez teorię informacji.

Myślę, że ten pomysł ma pewne zalety.