Czy sparametryzowana złożoność będzie przyszłością teorii złożoności?

Jestem naukowcem, który pracuje w teorii algorytmów i złożoności, do pewnego stopnia używam sparametryzowanej złożoności. Wydaje mi się, że badacze o sparametryzowanej złożoności są bardzo aktywni (nie mam na myśli, że inni nie) pod względem liczby prac badawczych. Widziałem, że badacze ze złożoności komunikacyjnej, złożoności arytmetycznej itp. Również w większym stopniu wykorzystują różne parametry.

Pytanie: Czy sparametryzowana złożoność będzie przyszłością teorii złożoności? Przyszłość oznacza po prostu liczbę prac badawczych, liczbę naukowców pracujących w tym obszarze itp.

Pamiętaj, że jestem naiwny i może nie być świadomy wielu rzeczy.

soft-question parameterized-complexity

— stary
źródło

Myślę, że tylko tak naprawdę twoje drugie pytanie jest odpowiednie dla tej witryny - a mianowicie, czy są prace nad „złożonością sparametryzowaną kwantowo”? - ponieważ pierwsze pytanie dotyczy (a) przewidywania przyszłości, która zawsze jest trudna, oraz (b) odpowiedzi byłyby bardzo subiektywne. Podejrzewam jednak, że odpowiedź na twoje pytanie (1) jest taka, że wciąż istnieje wiele aktywnych badań w zakresie algorytmów i złożoności, które nie dotyczą złożoności sparametryzowanej.

— Joshua Grochow,

Nie-badacz tutaj, ale nigdy nie wiedziałem, że sparametryzowana złożoność jest czymś innym niż ... złożonością. Co dokładnie robili ludzie, gdy złożoność zależała od dwóch wielkości? Zapomniałeś jednego z nich?

— user541686,

Jestem wielkim fanem sparametryzowanej złożoności i byłem podekscytowany tym postem tego samego dnia, w którym ukazał się biuletyn FPT. :)

— Michael Wehar

Przewidywanie przyszłości jest prawie niemożliwe, szczególnie w przypadku najnowszych badań. Nie sądzę, aby ktokolwiek przewidział, jak duży wpływ ma głębokie uczenie się, czy że kryptografia zostałaby przejęta przez zaciemnienie nie do odróżnienia.

Powiedziawszy to, powiem tyle: nie widzę żadnego konkretnego powodu, aby oczekiwać, że przejmą go sparametryzowane złożoności. To dojrzałe pole działające od około 20 lat. Tak naprawdę nie wydaje mi się, że jest to obszar rozwijający się. Dla jasności uważam, że jest to udany obszar, który nadal będzie się dobrze prosperować.

Jeśli spojrzysz na trendy Google , zainteresowanie wyszukiwaniem w sparametryzowanej złożoności maleje. (Jeśli jesteś zainteresowany, skorzystaj z innych terminów.) Jeśli spojrzysz na połączone cytaty z podręcznika Sparametryzowana złożoność Downey - Fellows i ich zaktualizowanego podręcznika , zobaczysz, że są one dość stabilne: _(Źródło:_{Google scholar}_{. Dodałem obie książki do mojego profilu, scaliłem je, zrobiłem zrzut ekranu połączonych cytatów, a następnie usunąłem je z mojego profilu).}

To zdrowa liczba cytowań, ale to nie wykładniczy wzrost sprawiłby, że myślisz, że zajmie się to sparametryzowana złożoność. Oczywiście dane te są bardzo błędne, ale jest to najlepszy wskaźnik, jaki mogę znaleźć na temat globalnej popularności sparametryzowanej złożoności.

Pamiętaj, że rzeczy mogą być bardzo popularne lokalnie, nawet jeśli nie są popularne na całym świecie. Kiedy byłem studentem, myślałem, że muszę się nauczyć teorii teorii, ponieważ wszyscy wokół mnie mówią o tym; Kupiłem nawet książkę. Potem przeszedłem do szkoły i nigdy więcej o tym nie słyszałem; książka pozostaje nieprzeczytana do dziś. Być może jesteś w podobnej sytuacji - jesteś w dziale, w którym dzieje się dużo sparametryzowanej złożoności, ale jeśli przeprowadzisz się gdzie indziej, historia będzie zupełnie inna.

— Tomasz
źródło

RIP do wszystkich tych nieprzeczytanych książek z teorii kategorii ...

— gigabajty

Po prostu z ciekawości: czy mówisz, że było miejsce, w którym wiele osób pracujących ze złożonością i algorytmami interesowało się przez jakiś czas teorią kategorii? Czy te osoby były bardziej w świecie języków programowania? (W takim przypadku nie byłoby to zaskakujące). Jako badacz teorii kategorii jestem ciekawy, gdzie było to miejsce i jakie było jego zainteresowanie.

— Damiano Mazza

@DamianoMazza Wpadłem w algorytmy i złożoność w szkole. Moja ekspozycja na teorię kategorii była po stronie PL / logiki rzeczy. Lubię teorię kategorii; po prostu niewiele się wydarzyło w mojej pracy.

— Thomas

Ok, jak już powiedziałem, nie jest to więc zaskakujące! (Ani, że ludzie PL / logiki są najbardziej zainteresowani kategoriami, ani że nie znalazłeś dla nich zastosowania w algorytmach i złożoności). Dziękuję Ci!

— Damiano Mazza

@DamianoMazza możesz stworzyć „pseudo-kategorię” baz TM i obliczyć ją przez jakąś słabą redukowalność, a następnie otrzymasz fajne rzeczy, takie jak zdolność do scharakteryzowania kompletności poprzez konstrukcje teoretyczne kategorii, ale wydaje mi się, kiedy to zrobiłem, że ty uzyskaj dokładnie takie same wyniki, po prostu używając zestawu. Jest taki artykuł, który został tu zamieszczony jakiś czas temu, nawiązując do tego: główne ideały w tym zestawie tworzą „klasy składniowe”, które mają kompletny język i są policzalne. Być może można uzyskać więcej przebiegów z odpowiedniej kategorii, ale nie dostałem żadnej.

— Samuel Schlesinger