Kategoria problemów NP-zupełnych?

Czy ma sens rozważenie kategorii wszystkich problemów związanych z NP-zupełnością, z morfizmami jako redukcjami wielomianów między różnymi instancjami? Czy ktoś kiedykolwiek opublikował artykuł na ten temat, a jeśli tak, to gdzie mogę go znaleźć?

Obszar, na który chcesz spojrzeć, nosi nazwę „teorii ukrytej złożoności”. Losowa i niekompletna garść nazwisk dla Google to Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca i Kazushige Terui.

Podstawową techniką jest powiązanie klas złożoności z podsystemami logiki liniowej (tzw. „Lekka logika liniowa”), przy założeniu, że eliminacja cięć w systemie logicznym powinna być kompletna dla danej klasy złożoności (np. LOGSPACE, PTIME itp.). Następnie poprzez Curry-Howard poznajesz język programowania, w którym dokładnie programy w danej klasie są wyraźne. Jak można się spodziewać po wzmiance o logice liniowej, wszystkie te systemy dają następnie monoidalne zamknięte kategorie różnych smaków, co pozostawia czysto algebraiczną i niezależną od maszyny charakterystykę różnych klas złożoności.

Jedną z rzeczy, które sprawiają, że ten obszar jest interesujący, jest to, że ani tradycyjna złożoność, ani metody logiczne / PL nie są całkowicie odpowiednie.

Ponieważ zaangażowane kategorie zazwyczaj mają zamkniętą strukturę, metody kombinatoryczne faworyzowane przez teoretyków złożoności często się psują (ponieważ programy wyższego rzędu mają tendencję do przeciwstawiania się kombinatorycznym charakterystykom). Typowym tego przykładem jest niepowodzenie metod syntaktycznych w radzeniu sobie z równoważnością kontekstową. Podobnie, metody semantyki również mają problemy, ponieważ często są zbyt ekstensywne (ponieważ tradycyjnie semantycy chcieli ukryć wewnętrzną strukturę funkcji). Najprostszym przykładem, jaki znam tutaj, jest zamknięcie LOGSPACE w składzie: jest to AFAIK możliwe tylko ze względu na połączenie typu „jaskółczy ogon” i selektywne ponowne obliczanie, a problemów nie można traktować jak czystych czarnych skrzynek.

Prawdopodobnie zechcesz też zaznajomić się z semantyką gry i Geometrią interakcji Girarda (i ich prekursorem, konkretnymi strukturami danych Kahna-Plotkina-Berry'ego), jeśli poważnie wejdziesz w ten obszar - idee przekazywania symbolicznych reprezentacji wyższych- obliczenia zamówieniowe użyte w tej pracy dostarczają wiele intuicji dla ICC.

Ponieważ wskazałem centralną rolę kategorii monoidalnych w tym dziele, możesz rozsądnie zastanawiać się nad powiązaniami z GCT Mulmuleya. Niestety nie mogę ci pomóc, ponieważ po prostu nie wiem wystarczająco dużo. Jednak Paul-André Melliès może być dobrym człowiekiem do poproszenia.

Można kategoryzować wiele rzeczy, ale to niekoniecznie oznacza, że ​​są to interesujące kategorie. Odpowiedź na pytanie „czy to ma sens” zależy od tego, co masz na myśli.

Jeśli chodzi o przewidywanie, czy byłoby to interesujące, załóżmy odpowiednią definicję redukcji, tak aby tworzyła kategorię, NPC. Kategoria teoretycznie interesujących pytań to takie pytania, jak pytanie, czy NPC ma różne limity czy limity (np. Produkty, produkty uboczne, wycofania, wypychania, ...). Dlatego przed przystąpieniem do formalizacji rzeczy dobrze byłoby usiąść i zastanowić się, co oznaczałyby te ograniczenia / ograniczenia i czy to znaczenie byłoby interesujące. Jeśli założymy, że NPC ma wady, to czy możliwość wycofania dwóch redukcji oznacza coś specjalnego? Takie pytania wydają się być interesujące, gdybyśmy chcieli dowiedzieć się, czym są „atomowe” problemy z całkowitą NP lub jak można połączyć wiele problemów z NP (lub ich redukcję);

Oto niektóre pytania: czy NPC ma jakieś interesujące podkategorie? czy NPC jest podkategorią jakichkolwiek interesujących większych kategorii? Wiemy już sporo o tym, w jaki sposób problemy z NP-zupełnością odnoszą się do innych klas problemów, więc domniemana odpowiedź na te pytania brzmi „oczywiście”. Ale, mówiąc dokładniej, co oferuje rozważenie tych relacji z perspektywy teoretycznej kategorii, czego nie oferują inne perspektywy? Jedną z rzeczy, które może zaoferować CT, jest pytanie, czy istnieją jakieś nietrywialne powiązania między NPC a inną kategorią. Oczywiście dopasowania są interesujące głównie wtedy, gdy kategorie za nimi same są interesujące, więc jeśli NPC nie ma dużo specjalnej struktury, to wiedza na temat dopasowania NPC tak naprawdę nie będzie zbyt duża.

Jeśli chodzi o konkretne referencje, nie znam żadnych podstron, ale linki w komentarzach Sadeqa, Ramprasad, Kaveha powinny gdzieś zacząć.