Überprüfung einer maximalen Antichain
In der Ordnungstheorie ist eine Antichain (Sperner-Familie / Unordnung) eine Teilmenge einer teilweise geordneten Menge mit der Eigenschaft, dass keine zwei Elemente miteinander vergleichbar sind. Eine maximale Antichain ist die Antichain, die in einer anderen Antichain nicht richtig enthalten ist. Nehmen wir den Kraftsatz von$\{1,2,\ldots, n\}$Als unser teilweise geordnetes Set wird hier die Reihenfolge durch Aufnahme angegeben. Dann ist meine Frage, ob es für eine gegebene Antichain dieser teilweise geordneten Menge einen Polynom-Zeit-Algorithmus gibt (in Bezug auf$n$) um zu überprüfen, ob diese Antichain tatsächlich "maximal" ist? Mit anderen Worten, Überprüfen, ob eine Teilmenge von$\{1,2,\ldots, n\}$ist entweder in der Antichain enthalten oder enthält einen Satz davon. Hier sollte ein solcher Algorithmus eine polynomielle Laufzeit für JEDE Antichain haben.
Update : Zur Verdeutlichung werde ich hier die Größe unserer Antichain als Parameter für den Verifizierungsalgorithmus behandeln. Mit anderen Worten, meine Frage ist: Gibt es einen Verifizierungsalgorithmus, dessen Laufzeit polynomisch ist?$n$ und $m$, wo $m$ist die Größe der Antichain. Wenn die Größe unserer Antichain$m$ ist exponentiell in $n$dann ist ein solcher Algorithmus trivial (nur diese Elemente einzeln vergleichen); aber wenn die gegebene Antichain O (Poly (n)) Größe hat, ist dies mein interessierter Fall. Zum Beispiel, wenn die Antichain von gegeben ist$\{\{1\}, \ldots, \{n\}\}$Wir müssen den Brute-Force-Vergleich sicherlich nicht durchführen.
Antworten
Anmerkung. Ursprünglich habe ich behauptet, dies sei eine vollständige Lösung, aber das war falsch, wie Emil in den Kommentaren gezeigt hat. Dieses Argument beweist jedoch die folgende schwächere Version.
Ich kann beweisen, dass es co-NP-vollständig ist, sich für eine Input-Familie zu entscheiden $A$ ob es einen Satz gibt $S$ das hat nichts mit allen Sets in zu tun $A$. Ich werde solche Familien maximal nennen. Dies zeigt, dass jeder mögliche Polynomzeitalgorithmus ausnutzen muss, dass die Eingabefamilie bereits für Eingaben mit linearer Größe eine Antichain ist. Meine Ermäßigung stammt von SAT.
Gegeben ein CNF $\Psi$ auf $n$ Variablen konvertieren wir es in eine Familie $A$ Über $2n$ Elemente, so dass $A$ ist genau dann maximal, wenn $\Psi$in unbefriedigend. Das$2n$ Elemente werden paarweise kommen, die ich mit bezeichne $i$ und $i'$.
Das Komplement jedes Paares ist in enthalten$A$ Egal ob $\Psi$, so $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Darüber hinaus fügen wir für jede Klausel eine Menge hinzu$A$ so dass wenn $x_i$ befindet sich in der Klausel, die die Menge enthält $i$, während wenn $\bar x_i$ befindet sich in der Klausel, die die Menge enthält $i'$. Zum Beispiel die Klausel$(x_i\vee \bar x_j)$ fügt das Set hinzu $ij'$ zu $A$.
Annehmen $\Psi$ist zufriedenstellend. Dann für eine zufriedenstellende Bewertung$x$, definieren Sie die Menge $S$ so dass $i\in S$ wenn $x_i$ ist falsch und $i'\in S$ wenn $x_i$ist wahr. Es ist einfach, das zu überprüfen$S$ steht in keinem Zusammenhang mit einem Element von $A$.
Nehme an, dass $A$ist nicht maximal. Nimm einen Satz$S$ nicht in Bezug auf irgendein Element von $A$. Definieren$x_i$ um wahr zu sein, wenn $i\notin S$ und falsch wenn $i'\notin S$, sonst willkürlich. Diese Definition ist in der Tat richtig, als$\overline{ii'}\in A$ impliziert, dass $i,i'\in S$Ist nicht möglich. Es ist einfach, das zu überprüfen$x$ ist eine zufriedenstellende Bewertung von $\Psi$.