最大の反鎖の検証
順序論では、反鎖（Spernerファミリー/クラッター）は半順序集合のサブセットであり、2つの要素が互いに比較できないという特性があります。最大の反鎖は、別の反鎖に適切に含まれていない反鎖です。のべき集合を取りましょう$\{1,2,\ldots, n\}$半順序集合として、ここでは順序は包含によって与えられます。次に、私の質問は、この部分的に調整されたセットの任意の反鎖について、（に関して）多項式時間アルゴリズムがあるかどうかです。$n$）この反鎖が実際に「最大」であることを確認するには？言い換えれば、のサブセットが$\{1,2,\ldots, n\}$反鎖に含まれているか、反鎖からのセットが含まれています。ここでは、そのようなアルゴリズムは、多項式のためのランタイムが必要ですANY antichainを。
更新：明確にするために、ここでは、検証アルゴリズムのパラメーターとして反鎖のサイズを扱います。言い換えれば、私の質問は次のとおりです。実行時間が多項式である検証アルゴリズムは存在しますか？$n$ そして $m$、 どこ $m$は反鎖のサイズです。私たちの反鎖のサイズが$m$ で指数関数的です $n$その場合、そのようなアルゴリズムは簡単です（これらの要素を1つずつ比較するだけです）。しかし、与えられた反鎖がO（poly（n））サイズである場合、これは私の興味のあるケースです。たとえば、反鎖がによって与えられるとき$\{\{1\}, \ldots, \{n\}\}$、私たちは確かに力ずくの比較を行う必要はありません。
回答
リマーク。もともと私はこれが完全な解決策であると主張しましたが、コメントでエミルが示したように、それは誤りでした。ただし、この引数は、次の弱いバージョンを証明します。
入力ファミリを決定することは共同NP完全であることを証明できます $A$ セットがあるかどうか $S$ それはのすべてのセットとは無関係です $A$。私はそのような家族を最大と呼びます。これは、可能な多項式時間アルゴリズムは、入力ファミリがすでに線形サイズの入力に対して反チェーンであることを利用する必要があることを示しています。私の削減はSATからです。
与えられたCNF $\Psi$ オン $n$ 変数、私たちはそれを家族に変換します $A$ 以上 $2n$ そのような要素、 $A$ が最大であるのは、 $\Psi$満足できない。ザ・$2n$ 要素はペアで提供されます。 $i$ そして $i'$。
すべてのペアの補集合はに含まれています$A$ かかわらず $\Psi$、 そう $\overline{11'}\in A$、 $\overline{22'}\in A$、...、 $\overline{nn'}\in A$。
さらに、すべての句に対して、セットを追加します$A$ そのような場合 $x_i$ が句に含まれている場合、セットには次のものが含まれます $i$、 $\bar x_i$ が句に含まれている場合、セットには次のものが含まれます $i'$。たとえば、句$(x_i\vee \bar x_j)$ セットを追加します $ij'$ に $A$。
仮定します $\Psi$充足可能です。その後、満足のいく評価のために$x$、セットを定義します $S$ そのような $i\in S$ もし $x_i$ 偽であり、 $i'\in S$ もし $x_i$本当です。それを確認するのは簡単です$S$ のどの要素とも関係がありません $A$。
仮定 $A$最大ではありません。セットを取る$S$ のどの要素とも関係ありません $A$。定義する$x_i$ 真実であるために $i\notin S$ とfalseの場合 $i'\notin S$、それ以外の場合は任意。この定義は確かに正しいです。$\overline{ii'}\in A$ ことを意味します $i,i'\in S$不可能である。それを確認するのは簡単です$x$ の満足のいく評価です $\Psi$。