Czy istnieje teoria łącząca teorię kategorii / algebrę abstrakcyjną i złożoność obliczeniową?

Teoria kategorii i algebra abstrakcyjna zajmują się sposobem łączenia funkcji z innymi funkcjami. Teoria złożoności dotyczy tego, jak trudna jest funkcja do obliczenia. Dziwne jest dla mnie to, że nie widziałem, aby ktoś łączył te kierunki studiów, ponieważ wydają się one takimi naturalnymi parami. Czy ktoś już to zrobił?

Jako motywujący przykład przyjrzyjmy się monoidom. Dobrze wiadomo, że jeśli operacja jest monoidem, wówczas możemy ją zrównoleglić.

Na przykład w Haskell możemy w trywialny sposób zdefiniować, że dodanie jest monoidą nad liczbami całkowitymi w następujący sposób:

instance Monoid Int where
    mempty = 0
    mappend = (+)

Teraz, jeśli chcemy obliczyć sumę od 0 do 999, moglibyśmy to zrobić sekwencyjnie:

foldl1' (+) [0..999]

lub moglibyśmy to zrobić równolegle

mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel

Ale równoległość tej monoidy ma sens tylko dlatego, że mappend działa w stałym czasie. Co by było, gdyby tak nie było? Listy, na przykład, są monoidami, w których mappend nie działa przez dłuższy czas (lub spację!). Zgaduję, że właśnie dlatego w Haskell nie ma domyślnej równoległej funkcji mconcat. Najlepsza implementacja zależy od złożoności monoidu.

Wydaje się, że powinien istnieć wygodny sposób na opisanie różnic między tymi dwoma monoidami. Powinniśmy wtedy być w stanie opatrzyć adnotacje naszym kodem tymi różnicami, a programy powinny automatycznie wybierać najlepsze algorytmy do zastosowania w zależności od złożoności monoidu.

[Złożoność obliczeniowa i teoria kategorii] wydają się być takimi naturalnymi parami.

Biorąc pod uwagę znaczenie złożoności obliczeniowej jako dziedziny badań, gdyby byli oni takimi naturalnymi podopiecznymi, może ktoś już zauważyłby związek?

Dzikie spekulacje. Niech zabawię czytelnika przemyśleniami na temat tego, dlaczego kategoryczne renderowanie złożoności obliczeniowej jest trudne. Prawdopodobnie kluczowy klaster koncepcji w teorii kategorii koncentruje się wokół uniwersalnych konstrukcji / właściwości (wraz z powiązanym aparatem funktorów, przekształceń naturalnych, przyłączy itp.). Jeśli możemy wykazać, że konstrukcja matematyczna ma uniwersalną właściwość, daje to wiele wglądu. Więc jeśli chcieliśmy kategorycznego podejścia do złożoności obliczeniowej, musielibyśmy znaleźć dogodną kategorię i pokazać, w jaki sposób kluczowe pojęcia teorii złożoności (np. LOGSPACE lub twardość NP) mogą być podane przez konstrukcje uniwersalne wykorzystujące tę kategorię. Nie zostało to jeszcze zrobione i myślę, że dzieje się tak, ponieważ jest to naprawdę trudny problem.

$T = T_1 \oplus T_2 \otimes T_3$$T_i$$\oplus, \otimes$¹ . Zamiast tego konstruujemy bazy TM, określając oddzielnie ich dwa komponenty: kontrolkę (FSM) i taśmę. Ani kontrola, ani taśma nie mają samych dobrych algebr.

Najpierw spójrzmy na taśmy. Istnieje kilka naturalnych sposobów komponowania taśm, z których żaden nie wydaje się działać w przypadku opisu składu baz TM.

• Sklej je jak zwykły dodatek. Nie jest to właściwe pojęcie, ponieważ taśmy są nieskończone i sklejając je jak porządek porządkowy, otrzymujemy podwójny nieskończony obiekt, który wykracza poza skończone obliczenia, prowadząc do obliczeń nieskończonych / hiperkomputerowych, które są interesujące jako matematyczne, ale nie odpowiadają wykonalne obliczenia.

• Trzymaj je równolegle , np. Dwie maszyny 3-głowicowe zamieniają się w maszyny 6-głowicowe. Nie mówi nam to, w jaki sposób komponenty współdziałają ze sobą.

• Taśmy z przeplotem. Jednym z problemów związanych z tym podejściem jest to, że nie jest jasne, jakie może być przeplatanie kanoniczne, jeśli w ogóle. Co więcej, przeplatanie „myli” istniejącą kontrolę, która zwykle jest precyzyjnie dostosowywana do określonego układu taśmy. Dlatego nie możemy ponownie użyć kontroli bezpośrednio.

$\pi$

Podsumowując, jesteśmy dość daleko od znacznego algebraicznego / kategorycznego traktowania złożoności obliczeniowej i potrzebowalibyśmy kilku pojęć koncepcyjnych, aby się tam dostać.

$\lambda$$\pi$$\lambda$$\pi$$\alpha$$\lambda$$\pi$

Ta odpowiedź na temat izomorfizmów między językami formalnymi łączy wyniki algebraiczne z teorii kodów z pojęciami z teorii kategorii, aby zbadać możliwe pojęcia równoważności i izomorfizmu między językami formalnymi a klasami złożoności.

Moją własną interpretacją tych wyników jest to, że punkty synchronizacji w słowach są różne dla deterministycznych i jednoznacznych niedeterministycznych przetworników, a nawet różne między deterministycznymi przetwornikami do przodu i deterministycznymi do tyłu. Przyjmując tę ​​perspektywę punktów synchronizacji, można połączyć te wyniki z widocznymi językami przesuwania w dół i rodzi pytanie, czy powinny one również uwzględniać proste separatory (takie jak spacja lub przecinek) oprócz połączeń i zwrotów. (Domyślam się, że separator może być emulowany przez połączenie powrotne + wywołanie, ale ponieważ wymagają one dwóch symboli zamiast jednego, nie jest dla mnie jasne, czy to wystarczy. Mogą istnieć również widoczne języki, które mają tylko separatory, ale nie symbole połączeń lub zwrotów).