Weryfikacja maksymalnego antychaina
W teorii porządku antychain (rodzina Sperner / bałagan) jest podzbiorem częściowo uporządkowanego zbioru, z tą właściwością, że żadne dwa elementy nie są ze sobą porównywalne. Maksymalny antychain to antychain, który nie jest właściwie zawarty w innym antychainie. Weźmy zestaw mocy$\{1,2,\ldots, n\}$jako nasz częściowo uporządkowany zestaw, tutaj kolejność jest podana przez włączenie. W takim razie moje pytanie brzmi, czy dla dowolnego antychaina tego częściowo uporządkowanego zbioru istnieje algorytm wielomianu (w odniesieniu do$n$), aby sprawdzić, czy ten antychain jest rzeczywiście „maksymalny”? Innymi słowy, sprawdzenie, czy jakikolwiek podzbiór$\{1,2,\ldots, n\}$jest albo zawarta w antychainie, albo zawiera jakiś zestaw. Tutaj taki algorytm powinien mieć wielomian Czas przebiegu JAKIEJKOLWIEK antyłańcuch.
Aktualizacja : Aby wyjaśnić, potraktuję tutaj rozmiar naszego antychaina jako parametr algorytmu weryfikacji. Innymi słowy, moje pytanie brzmi: czy istnieje algorytm weryfikacji, którego czas wykonywania jest wielomianowy$n$ i $m$, gdzie $m$jest wielkością antychaina. Kiedy rozmiar naszego antychaina$m$ jest wykładniczy w $n$wtedy taki algorytm jest trywialny (po prostu porównuje te elementy jeden po drugim); ale kiedy dany antychain ma rozmiar O (poly (n)), to jest to mój interesujący przypadek. Na przykład, gdy antychain jest podany przez$\{\{1\}, \ldots, \{n\}\}$, z pewnością nie musimy robić porównania brutalnej siły.
Odpowiedzi
Uwaga. Początkowo twierdziłem, że jest to pełne rozwiązanie, ale było to fałszywe, jak pokazał Emil w komentarzach. Jednak ten argument dowodzi następującej słabszej wersji.
Mogę udowodnić, że decyzja o rodzinie wejściowej jest co-NP-kompletna $A$ czy jest zestaw $S$ to nie jest związane ze wszystkimi zestawami w $A$. Nazwałbym takie rodziny maksymalnymi. To pokazuje, że każdy możliwy algorytm czasu wielomianowego musi wykorzystywać to, że rodzina danych wejściowych jest antychainem, już dla wejść o rozmiarze liniowym. Moja redukcja pochodzi z SAT.
Biorąc pod uwagę CNF $\Psi$ na $n$ zmienne, zamieniamy je na rodzinę $A$ nad $2n$ elementy, takie że $A$ jest maksymalny wtedy i tylko wtedy, gdy $\Psi$w niezadowalającym. Plik$2n$ elementy będą występować w parach, co oznaczam przez $i$ i $i'$.
Dopełnienie każdej pary jest zawarte w$A$ niezależnie od tego $\Psi$, więc $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Ponadto dla każdej klauzuli dodajemy zestaw do$A$ takie, że jeśli $x_i$ jest w klauzuli, zestaw zawiera $i$, podczas gdy jeśli $\bar x_i$ jest w klauzuli, zestaw zawiera $i'$. Na przykład klauzula$(x_i\vee \bar x_j)$ dodaje zestaw $ij'$ do $A$.
Przypuszczać $\Psi$jest satysfakcjonujący. Następnie dla satysfakcjonującej oceny$x$zdefiniuj zestaw $S$ takie że $i\in S$ gdyby $x_i$ jest fałszywe i $i'\in S$ gdyby $x_i$jest prawdziwy. Łatwo to sprawdzić$S$ nie ma związku z żadnym elementem $A$.
Przypuszczam, że $A$nie jest maksymalna. Weź zestaw$S$ nie w związku z żadnym elementem $A$. Definiować$x_i$ aby było prawdą, jeśli $i\notin S$ i fałsz, jeśli $i'\notin S$, inaczej arbitralnie. Ta definicja jest rzeczywiście poprawna, jak$\overline{ii'}\in A$ to sugeruje $i,i'\in S$nie jest możliwe. Łatwo to sprawdzić$x$ jest satysfakcjonującą oceną $\Psi$.