Czy liczenie maksymalnych klików na wykresie nieporównywalności # P jest kompletne?

13

To pytanie jest motywowane pytaniem MathOverflow Peng Zhanga . Valiant wykazał, że zliczanie maksymalnych klików na wykresie ogólnym jest zakończone metodą # P, ale co jeśli ograniczymy się do wykresów nieporównywalności (tzn. Chcemy policzyć maksymalne antichains w skończonym zestawie)? To pytanie wydaje się na tyle naturalne, że podejrzewam, że zostało wcześniej rozważone, ale nie udało mi się znaleźć go w literaturze.

Timothy Chow
źródło

Odpowiedzi:

11

Zgodnie z tym streszczeniem dla „Złożoności liczenia cięć i obliczania prawdopodobieństwa połączenia wykresu” (SIAM J. Comput. 12 (1983), s. 777-788), liczenie antyłańcuchów w częściowej kolejności wynosi # P-kompletne. Nie mam dostępu do tego artykułu, więc nie wiem, czy ten wynik obejmuje maksymalne anty-łańcuchy, czy nie.

mum
źródło
@ András: Myślę, że ich wynikiem jest liczenie antichains (które niekoniecznie są maksymalne). Może być łatwo zauważyć, że liczenie maksymalnych antichains jest również # P-complete, ale nie widzę tego.
Tsuyoshi Ito,
@ András: Pytanie dotyczy maksymalnych antichains, a nie antichains o maksymalnej liczności. Nie badałem redukcji w pracy, więc może ich zmniejszenie dowodzi również kompletności # P liczenia maksymalnych antichains w tym samym czasie, ale przynajmniej są to różne problemy.
Tsuyoshi Ito
@Tsuyoshi: masz rację, papier Provan / Ball pokazuje tylko, że liczenie antychainsów o maksymalnej liczności jest trudne. Powrót do deski kreślarskiej ...
András Salamon,
8
W rzeczywistości, jeśli spojrzysz na dowód, zobaczysz, że # P-kompletność jest udowodniona dla klasy zestawów, w których wszystkie maksymalne antichains mają tę samą liczność. Mianowicie, zacznij od dowolnego dwustronnego wykresu z wierzchołków i zbuduj dwuczęściowy wykres z wierzchołkami, dodając nowych wierzchołków i nowych krawędzi . Następnie, jeśli i jest zestawem wierzchołków , zdefiniuj poset na , ustawiając jeśli in G 2 n n n { ( v , v ) : v V } V 1 V 2 G V 1V 2 x < y x V 1 y V 2 x y G G=(V,E)nG2nn{v:vV}n{(v,v):vV}V1V2GV1V2x<yxV1yV2 , a i przylegają do siebie w . To odpowiada na moje pytanie. xyG
Timothy Chow,