Verifica di un anticatena massimale
Nella teoria dell'ordine, un'anticatena (famiglia Sperner / disordine) è un sottoinsieme di un insieme parzialmente ordinato, con la proprietà che due elementi non sono confrontabili tra loro. Un anticatena massimo è l'anticatena che non è propriamente contenuto in un altro anticatena. Prendiamo il set di potenza di$\{1,2,\ldots, n\}$come il nostro set parzialmente ordinato, qui l'ordine è dato dall'inclusione. Quindi la mia domanda è, per ogni data anticatena di questo insieme parzialmente ordinato, esiste un algoritmo tempo polinomiale (rispetto a$n$) per verificare che questo anticatena sia effettivamente "massimale"? In altre parole, verificando che qualsiasi sottoinsieme di$\{1,2,\ldots, n\}$è contenuto o contiene un set dell'anticatena. Qui tale algoritmo dovrebbe avere un tempo di esecuzione polinomiale per QUALSIASI anticatena.
Aggiornamento : per chiarire, qui tratterò la dimensione del nostro anticatena come parametro per l'algoritmo di verifica. In altre parole, la mia domanda è: esiste un algoritmo di verifica, il cui tempo di esecuzione è polinomiale in$n$ e $m$, dove $m$è la dimensione dell'anticatena. Quando le dimensioni del nostro anticatena$m$ è esponenziale in $n$allora tale algoritmo è banale (basta confrontare quegli elementi uno per uno); ma quando l'anticatena data ha dimensione O (poly (n)), questo è il mio caso interessato. Ad esempio, quando l'anticatena è dato da$\{\{1\}, \ldots, \{n\}\}$, certamente non dobbiamo fare il confronto della forza bruta.
Risposte
Nota. Inizialmente ho affermato che questa fosse una soluzione completa, ma era falso, come mostrato da Emil nei commenti. Tuttavia, questo argomento dimostra la seguente versione più debole.
Posso dimostrare che è co-NP-completo decidere per una famiglia di input $A$ se c'è un set $S$ che non è correlato a tutti gli insiemi in $A$. Chiamerò queste famiglie al massimo. Ciò mostra che ogni possibile algoritmo temporale polinomiale deve sfruttare che la famiglia di input è un'anticatena, già per ingressi di dimensione lineare. La mia riduzione è da SAT.
Dato un CNF $\Psi$ sopra $n$ variabili, lo convertiamo in una famiglia $A$ al di sopra di $2n$ elementi, tale che $A$ è massimo se e solo se $\Psi$in insoddisfacente. Il$2n$ gli elementi verranno in coppia, che denoto con $i$ e $i'$.
Il complemento di ogni coppia è contenuto in$A$ indipendentemente da $\Psi$, così $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Inoltre, per ogni clausola aggiungiamo un set a$A$ tale che se $x_i$ è nella clausola, l'insieme contiene $i$, mentre se $\bar x_i$ è nella clausola, l'insieme contiene $i'$. Ad esempio, la clausola$(x_i\vee \bar x_j)$ aggiunge il set $ij'$ per $A$.
Supponiamo $\Psi$è soddisfacente. Quindi per una valutazione soddisfacente$x$, definire l'insieme $S$ tale che $i\in S$ Se $x_i$ è falso e $i'\in S$ Se $x_i$è vero. È semplice verificarlo$S$ non è in relazione con alcun elemento di $A$.
Supporre che $A$non è massimale. Prendi un set$S$ non in relazione con alcun elemento di $A$. Definire$x_i$ per essere vero se $i\notin S$ e falso se $i'\notin S$, altrimenti arbitrariamente. Questa definizione è davvero corretta, come$\overline{ii'}\in A$ implica che $i,i'\in S$non è possibile. È semplice verificarlo$x$ è una valutazione soddisfacente di $\Psi$.