Проверка максимальной антицепи
В теории порядка антицепь (семейство Спернера / беспорядок) - это подмножество частично упорядоченного множества, обладающее тем свойством, что никакие два элемента не могут быть сопоставимы друг с другом. Максимальная антицепь - это антицепь, которая не содержится должным образом в другой антицепи. Возьмем силовой набор$\{1,2,\ldots, n\}$как наш частично упорядоченный набор, здесь порядок определяется включением. Тогда мой вопрос: для любой данной антицепи этого частично упорядоченного множества существует какой-либо алгоритм с полиномиальным временем (относительно$n$), чтобы убедиться, что эта антицепь действительно "максимальная"? Другими словами, проверка того, что любое подмножество$\{1,2,\ldots, n\}$либо содержится в, либо содержит некоторый набор из антицепи. Здесь такой алгоритм должен иметь полиномиальное время выполнения для ЛЮБОЙ антицепи.
Обновление : чтобы уточнить, здесь я буду рассматривать размер нашей антицепи как параметр для алгоритма проверки. Другими словами, мой вопрос: существует ли алгоритм проверки, время выполнения которого полиномиально от$n$ а также $m$, где $m$размер антицепи. Когда размер нашей антицепи$m$ экспоненциально в $n$тогда такой алгоритм тривиален (просто сравнивая эти элементы один за другим); но когда данная антицепь имеет размер 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$ и ложь, если $i'\notin S$, в противном случае произвольно. Это определение действительно верно, так как$\overline{ii'}\in A$ подразумевает, что $i,i'\in S$это невозможно. Несложно проверить, что$x$ удовлетворительная оценка $\Psi$.