Po co używać języków w teorii złożoności

Właśnie zaczynam wchodzić w teorię obliczeń, która bada, co można obliczyć, jak szybko, z wykorzystaniem ilości pamięci iz jakim modelem obliczeniowym.

Mam dość podstawowe pytanie, ale naprawdę mam nadzieję, że niektórzy z was pomogą mi zrozumieć koncepcję:

Dlaczego wszystko koncentruje się wokół pojęcia i definicji JĘZYKÓW (tj. Języków zwykłych i języków bezkontekstowych)? W jaki sposób odnoszą się one i opisują złożoność algorytmu oraz możliwe modele obliczeniowe do ich rozwiązania?

Czytam podobne pytania:

ale wciąż nie mam odpowiedzi na moje wątpliwości, ponieważ dostarczają one praktycznego uzasadnienia, dlaczego są ważne (co rozumiem), ale nie pomagają mi zrozumieć, dlaczego na nich opiera się teoria złożoności.

complexity-theory formal-languages

— Matteo
źródło

Czy to nie obejmuje naszych pytań referencyjnych ?

— Raphael

@Raphael - Dziękujemy za zwrócenie mi uwagi na to pytanie, jest to świetna referencja! Czytam to teraz, ale obecnie uważam, że może to być uzupełnienie pytania cs.stackexchange.com/questions/13669/… . Wydaje mi się, że nie ma już odpowiedzi. Daj mi znać, jeśli będziesz chudy inaczej

— Matteo

Język jest tylko zbiorem łańcuchów o skończonej długości, który jest taki sam jak funkcja, która odwzorowuje łańcuchy o skończonej długości na 1 lub 0. Więc naprawdę pytasz „dlaczego jest tyle teorii złożoności dotyczącej problemów decyzyjnych”, a odpowiedź brzmi: najprostszy (nietrywialny) rodzaj zadań obliczeniowych i często bardziej skomplikowane zadania obliczeniowe można sprowadzić do problemów decyzyjnych.

— Sasho Nikolov

Odpowiedzi:

To dlatego, że języki są najlepszym (jedynym?) Sposobem sformalizowania pojęcia „problemu”.

$L$

$10^6$ $10^9$ $10^{12}$

Po drugie, języki są po prostu ładną abstrakcją danych. Potrzebujesz czegoś, na co możesz zrobić dowody, czegoś, co możesz formalnie modelować. Kodowanie danych wejściowych i wyjściowych w postaci ciągu oznacza, że nie masz teraz do czynienia z bitami w pamięci, ale z obiektami matematycznymi o określonych właściwościach. Możesz o nich wnioskować i udowodnić ich dowody w sposób formalny i bardzo prosty.

$k$

Oto moje wyzwanie: znajdź sposób, aby matematycznie opisać problemy, które nie są językami. Nie wiem, czy języki są wyjątkowe, ale myślę, że to najprostsze narzędzie, jakie mamy, najłatwiejsze w obsłudze.

— jmite
źródło

Języki z pewnością nie są jedynym sposobem formułowania problemów. Na przykład możesz sformalizować coś takiego jak liczba chromatyczna jako funkcja od wykresów do liczb naturalnych. W rzeczywistości jest sporo pracy nad problemami z funkcjami i optymalizacją.

— David Richerby

To prawda, ale jak poradziłbyś sobie ze złożonością obliczania liczby chromatycznej bez jakiegoś pojęcia języka lub maszyny?

— jmite

Dzięki za odpowiedź, rozumiem. Jednak wciąż mam 2 pytania: 1) czy fakt, że używamy języków, nie wpłynie na wyniki dotyczące złożoności lub rozstrzygalności problemu? tj. czy problem może być rozwiązany w arytmetyki zmiennoprzecinkowej, ale nie w arytmetyki liczb całkowitych (tj. programowanie liczb całkowitych)? 2) Jak wykonujemy to odwzorowanie z dowolnego rodzaju danych na unikalny język, który opisuje je wszystkie (skoro chcemy ocenić złożoność problemu i abstrahować od konkretnych danych wejściowych)? Dzięki jeszcze raz!

— Matteo

@jmite Potrzebujesz maszyny, tak, ale niekoniecznie języka.

— Raphael

@ Rafael wiele klas złożoności, które są zwykle definiowane pod względem czasu działania maszyn, można scharakteryzować pod względem złożoności opisowej.

— Sasho Nikolov

Istnieją dwie podstawowe odpowiedzi na twoje pytanie:

Teoria złożoności to coś więcej niż języki, na przykład klasy funkcji, złożoność arytmetyczna oraz podobszary algorytmów aproksymacji i niedopuszczalności.
Powody historyczne: jednym z podstawowych artykułów z teorii obliczalności było omówienie Entscheidungsproblem Hilberta (forma problemu zatrzymania).

Niestety niewiele wiem o tym drugim, ale pozwól mi rozwinąć ten pierwszy.

Złożoność poza językami

$L$ $M$ $f_M$ $x \in M$ $f_M(x) \in L$ .

Złożoność obwodu arytmetycznego (lub teoria złożoności algebraicznej ) dotyczy złożoności obliczania różnych wielomianów. Ważnymi klasami złożoności są tutaj VP i VNP, a teoria złożoności geometrycznej jest ważnym projektem próbującym oddzielić VP i VNP (a później P i NP) z wykorzystaniem geometrii algebraicznej i teorii reprezentacji.

Innym ważnym przykładem złożoności algebraicznej jest szybkie mnożenie macierzy. Tutaj podstawowe pytanie brzmi: jak szybko możemy pomnożyć dwie macierze ? Podobne pytania dotyczą tego, jak szybko możemy pomnożyć liczby całkowite, jak szybko możemy przetestować liczby całkowite pod kątem pierwszeństwa (jest to problem decyzyjny!) I jak szybko możemy uwzględnić liczby całkowite.

Wypukła optymalizacja dotyczy problemów optymalizacyjnych, które można skutecznie (lub prawie rozwiązać) skutecznie. Przykładami są programowanie liniowe i półfinałowe, z których oba mają wydajne algorytmy. Tutaj interesuje nas zarówno optymalne, jak i samo optymalne rozwiązanie. Ponieważ często istnieje więcej niż jedno optymalne rozwiązanie, obliczenie optymalnego rozwiązania nie jest dobrze reprezentowane jako problem decyzyjny.

$\ln n$

— Yuval Filmus
źródło

Spójrzmy na to pytanie z perspektywy teorii kategorii. Problemy decyzyjne (lub języki) odpowiadałyby wówczas przedmiotom kategorii, a dozwolone redukcje między dwoma problemami odpowiadałyby morfizmom (strzałkom) kategorii.

Mówienie o językach ma tę zaletę, że równoważność języków jest dobrze zdefiniowana (mianowicie przez równość ekstensywną). Dwa niezwiązane ze sobą problemy mogą prowadzić do tego samego języka, a następnie możemy uznać je za równoważne. Jeśli zamiast tego chcielibyśmy porozmawiać o problemach izomorficznych, musielibyśmy zdefiniować dozwolone morfizmy między dwoma problemami. Ale dozwolone morfizmy zależą od rozważanej faktycznej klasy złożoności, co czyni to podejście mniej odpowiednim do porównywania różnych klas złożoności.

Pojęcie problemów izomorficznych będzie zwykle grubsze niż pojęcie równoważnych języków, tzn. Dwa problemy mogą być izomorficzne, nawet jeśli ich powiązane języki nie są równoważne. Co gorsza, często istnieją różne rozsądne pojęcia dotyczące dozwolonych morfizmów, które są zgodne tylko w odniesieniu do dozwolonych izomorfizmów. Skupienie się na językach pozwala odłożyć takie problemy, dopóki nie będziemy mieli ochoty rozmawiać o różnych rozsądnych pojęciach redukcji (takich jak redukcja Karp vs. redukcja Cooka).

— Thomas Klimpel
źródło

To nie wydaje się odpowiadać na pytanie. Nadal można mówić o morfizmach między problemami, bez względu na to, jakie przedmioty są używane w odpowiedniej kategorii.

— David Richerby,

@DavidRicherby Chciałem zwrócić uwagę na to, że przybicie odpowiednich morfizmów jest trudniejsze niż przybicie odpowiednich obiektów (= języków). (Zwłaszcza, że zwykle istnieje więcej niż jedno właściwe pojęcie morfizmów.) Bez morfizmów nie można mówić o problemach izomorficznych (lub algorytmach). Jednak języki pozwalają ci mówić o równoważności problemów. Być może nie wyjaśniłem tego poprawnie, ale (dla mnie) jest to dobry powód „używania języków w teorii złożoności”.

— Thomas Klimpel