최대 안티 체인 검증
주문 이론에서 안티 체인 (Sperner 패밀리 / 클러 터)은 부분적으로 정렬 된 집합의 하위 집합으로, 두 요소가 서로 비교할 수 없다는 속성이 있습니다. 최대 안티 체인은 다른 안티 체인에 제대로 포함되지 않은 안티 체인입니다. 파워 세트를 가져 가자$\{1,2,\ldots, n\}$부분적으로 주문 된 세트로 여기에 포함 된 순서입니다. 그런 다음 내 질문은 이 부분적으로 정렬 된 집합의 주어진 안티 체인에 대해 다항식 시간 알고리즘이 있습니까?$n$)이 안티 체인이 실제로 "최대"인지 확인하려면? 즉,$\{1,2,\ldots, n\}$안티 체인에 포함되거나 일부 세트를 포함합니다. 여기서 그러한 알고리즘은 모든 안티 체인에 대한 다항식 런타임을 가져야합니다 .
업데이트 : 명확히하기 위해 여기서는 검증 알고리즘의 매개 변수로 안티 체인의 크기를 취급 할 것입니다. 즉, 내 질문은 : 런타임이 다항식 인 검증 알고리즘이 있습니까?$n$ 과 $m$, 어디 $m$안티 체인의 크기입니다. 안티 체인의 크기가$m$ 기하 급수적이다 $n$그런 알고리즘은 사소합니다 (단지 요소를 하나씩 비교하는 것입니다). 그러나 주어진 안티 체인이 O (poly (n)) 크기를 가질 때, 이것은 내 관심 사례입니다. 예를 들어, 안티 체인이$\{\{1\}, \ldots, \{n\}\}$, 우리는 확실히 무차별 대입 비교를 할 필요가 없습니다.
답변
말. 원래 나는 이것이 완전한 해결책이라고 주장했지만 Emil이 의견에서 보여준 것처럼 그것은 거짓이었습니다. 그러나이 주장은 다음과 같은 약한 버전을 증명합니다.
입력 패밀리를 결정하는 것이 공동 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$, if $\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$.