Kategoria problemów NP-zupełnych?

28

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źć?

Paul Allen Grubbs
źródło
1
Nie jestem pewien, dlaczego chcesz kategorii wyłącznie problemów NP-zupełnych, ale kategoria wszystkich problemów decyzyjnych z pewnym ustalonym pojęciem redukcji (takich jak wielomianowe redukcje wielokrotne jeden raz) jako morfizmów wydaje się rozsądnym przedmiotem do rozważenia. W ogóle nie znam teorii kategorii i nie mogę zgadnąć, czy jest interesująca, czy nie.
Tsuyoshi Ito,
1
Nie jestem pewien, czy to pomaga, ale dam temu szansę: na izomorfizmy i gęstość NP i innych kompletnych zestawów . Zobacz także wersję czasopisma . Zobacz także artykuł Mahaneya .
MS Dousti,
2
Chciałem tylko rozwinąć komentarz Sadeqa. Izomorfizm między -Complete problemów badano i wiele pracy zostało zrobione w kierunku udowodnienia / podważania przypuszczeń Berman-Hartmanis (który stanowi, że wszyscy N P -Complete problemem są „izomorficzne” w czasie wielomianowym wiele-jeden redukcje) . Oto ankieta przeprowadzona przez Manindrę Agrawal na temat hipotezy izomorfizmu ( cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf ). NPNP
Ramprasad
1
@Tsuyoshi: nawet kategoria problemów NPC z obniżeniem Karp może być potencjalnie interesująca - gdybyśmy naprawdę zrozumieli nawet tę kategorię, mielibyśmy znacznie lepsze zrozumienie złożoności w ogóle (ponieważ prawdopodobnie pociągałoby to za sobą znacznie lepsze zrozumienie Karp redukcje, stąd czas wielomianowy). OTOH, nie jestem pewien, czy postrzeganie go jako kategorii zapewni sposób na zrozumienie. W przeszłości myślałem o tym problemie i szukałem referencji, które widzą złożoność w ten sposób i nie znalazłem. Mam nadzieję, że ktoś to zrobi!
Joshua Grochow
3
Popieram Jozuego. Ważne jest to, że nie można zdefiniować kategorii, ważne jest znalezienie w niej interesującej struktury kategorycznej. W przypadku obliczalności istnieją interesujące struktury, ale ze względu na złożoność nie wiem. Andrej powinien wiedzieć lepiej i mam nadzieję, że sprawdzi to pytanie.
Kaveh,

Odpowiedzi:

21

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.

Neel Krishnaswami
źródło
16

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ąć.

strzyżyk romano
źródło