Vérification d'une antichaine maximale
Dans la théorie de l'ordre, une antichaïne (famille de Sperner / clutter) est un sous-ensemble d'un ensemble partiellement ordonné, avec la propriété qu'aucun élément n'est comparable entre eux. Une antichaine maximale est l'antichaine qui n'est pas correctement contenue dans une autre antichaine. Prenons l'ensemble de puissance de$\{1,2,\ldots, n\}$comme notre ensemble partiellement ordonné, ici l'ordre est donné par inclusion. Alors ma question est, pour toute antichaîne donnée de cet ensemble partiellement ordonné, y a-t-il un algorithme$n$) pour vérifier que cette antichaïne est bien "maximale"? En d'autres termes, vérifier que tout sous-ensemble de$\{1,2,\ldots, n\}$est soit contenu dans, soit contient un ensemble de l'antichaïne. Ici, un tel algorithme devrait avoir un temps d'exécution polynomial pour N'IMPORTE QUELLE antichaine.
Mise à jour : Pour clarifier, ici je traiterai la taille de notre antichain comme le paramètre de l'algorithme de vérification. En d'autres termes, ma question est: existe-t-il un algorithme de vérification, dont l'exécution est polynomiale en$n$ et $m$, où $m$est la taille de l'antichaïne. Quand la taille de notre antichain$m$ est exponentielle en $n$alors un tel algorithme est trivial (il suffit de comparer ces éléments un par un); mais quand l'antichaïne donnée a la taille O (poly (n)), c'est mon cas intéressé. Par exemple, lorsque l'antichaïne est donnée par$\{\{1\}, \ldots, \{n\}\}$, nous n'avons certainement pas à faire la comparaison par force brute.
Réponses
Remarque. À l'origine, j'ai prétendu que c'était une solution complète, mais c'était faux, comme l'a montré Emil dans les commentaires. Cependant, cet argument prouve la version plus faible suivante.
Je peux prouver qu'il est co-NP-complet de décider d'une famille d'entrée $A$ s'il y a un ensemble $S$ qui n'est pas lié à tous les ensembles de $A$. J'appellerai ces familles maximales. Cela montre que tout algorithme de temps polynomial possible doit exploiter le fait que la famille d'entrée est une antichaîne, déjà pour des entrées de taille linéaire. Ma réduction vient de SAT.
Étant donné un CNF $\Psi$ au $n$ variables, nous le convertissons en famille $A$ plus de $2n$ éléments, tels que $A$ est maximal si et seulement si $\Psi$en insatisfiable. le$2n$ les éléments viendront par paires, ce que je désigne par $i$ et $i'$.
Le complément de chaque paire est contenu dans$A$ outre le fait que $\Psi$, donc $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
De plus, pour chaque clause, nous ajoutons un ensemble à$A$ tel que si $x_i$ est dans la clause, l'ensemble contient $i$, tandis que si $\bar x_i$ est dans la clause, l'ensemble contient $i'$. Par exemple, la clause$(x_i\vee \bar x_j)$ ajoute l'ensemble $ij'$ à $A$.
Supposer $\Psi$est satisfaisable. Alors pour une évaluation satisfaisante$x$, définissez l'ensemble $S$ tel que $i\in S$ si $x_i$ est faux et $i'\in S$ si $x_i$est vrai. Il est simple de vérifier que$S$ n'est en relation avec aucun élément de $A$.
Supposer que $A$n'est pas maximal. Prenez un ensemble$S$ pas en relation avec aucun élément de $A$. Définir$x_i$ pour être vrai si $i\notin S$ et faux si $i'\notin S$, sinon arbitrairement. Cette définition est en effet correcte, car$\overline{ii'}\in A$ implique que $i,i'\in S$n'est pas possible. Il est simple de vérifier que$x$ est une évaluation satisfaisante de $\Psi$.