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

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

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,

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 i

G = (V, E)

$G=(V,E)$

n

$n$

G^{'}

$G'$

2 n

$2n$

n

$n$

{v^{'} : v \in V}

$\{v' : v\in V\}$

n

$n$

{(v, v^{'}) : v \in V}

$\{(v,v'): v\in V\}$

V_{1}

$V_1$

V_{2}

$V_2$

G^{'}

$G'$

V_{1} \cup V_{2}

$V_1\cup V_2$

x < y

$x<y$

x \in V_{1}

$x\in V_1$

y \in V_{2}

$y\in V_2$ , a i przylegają do siebie w . To odpowiada na moje pytanie.

x

$x$

y

$y$

G^{'}

$G'$

— Timothy Chow,