이 문제를 NP 하드로 표시하려는 첫 번째 시도는 잘못되었습니다. 크기 2 또는 4의 조합 만 허용된다는 사실을 고려하지 않았기 때문입니다. 그러나 Jim D.'s suggestion을 사용하여 3-dimensional matching (3DM)을 줄이면 NP를 어렵다는 것을 알 수 있습니다.
문제의 자연 결정 문제 양식 ("개체의 집합 O 및 O 또는 정수 m의 2 개 또는 4 개의 개체 조합의 집합 C가 주어 졌다고 가정하면 D의 모든 집합이 pairwise disjoint이고 D의 모든 집합의 합집합이 적어도 m? "이되는 C의 집합 D)는 NP 하드입니다. 분명히 최적화 문제 (즉, m을 최대화하는 조합의 실제 하위 집합을 찾는 원래 문제)는이 문제만큼 어렵지 않습니다. (최적화 문제가 결정 문제보다 "많이"더 어렵지 않다는 것을 알기 위해, 각 단계에서 의사 결정 문제를 풀 때 이진 검색을 사용하여 솔루션이 존재하는 최대 m 값을 먼저 찾을 수 있고, 일단이 최대 m 값이 발견되면 각 조합이 차례로 제거되는 일련의 결정 문제를 해결합니다. 특정 조합을 제거한 후 솔루션이 여전히 "예"이면, 모든 조합을 제거 할 수도 있습니다 미래의 문제 인스턴스가 될 것이며 솔루션이 "아니오"가되면 솔루션에이 조합을 유지해야합니다.)
3DM의 인스턴스 (X, Y, Z, T, k)가 주어지면, X, Y 및 Z는 서로 쌍을 이루지 않는 세트이고, T는 X * Y * Z의 서브 세트 , X, Y, Z로부터 각각 제 1, 제 2 및 제 3 성분을 갖는 순서화 된 트리플의 세트) 및 k는 정수이고, 우리의 작업은 | T |의 서브 세트 U가 존재하는지 여부를 결정하는 것이다. > = k이고 U의 모든 트리플은 쌍으로 떨어져 있습니다 (즉, "T에 적어도 k 개의 중복되지 않는 트리플이 있습니까?"). 3DM의 이러한 인스턴스를 문제의 인스턴스로 전환하려면 T에있는 각각의 트리플에서 새로운 4 개 조합을 생성하고 각각에 고유 한 더미 값을 추가하면됩니다. 생성 된 문제 인스턴스의 개체 집합은 X, Y, Z 및 T | 우리가 만든 더미 값. 마지막으로, m을 k로 설정하십시오.
원래 3DM 인스턴스에 대한 답이 "예"라고 가정합니다. 즉, T에 적어도 k 개의 중첩되지 않는 트리플이 있습니다. 그런 솔루션에서 k 개의 트리플이 각각 당신의 문제에 C를 입력하십시오.이 4 가지 조합 중 두 가지가 겹치지 않습니다. 왜냐하면 건설을 통해 4 번째 요소가 모두 구별되고, 따라서 문제의 인스턴스에는 적어도 m = k 개의 중첩되지 않는 4 개 조합이 있으므로 해당 문제에 대한 솔루션은 "예"여야합니다.
다른 방향에서, 문제의 구성된 인스턴스에 대한 해답이 "예"라고 가정합니다. 즉, C에 겹치지 않는 4 가지 이상의 4 가지 조합이 있다고 가정합니다. 각각의 4 개 조합 (네 번째를 던져 버림)을 사용하여 T에서 k = m 개의 중첩되지 않는 트리플 세트를 생성하므로 원본 3DM 인스턴스에 대한 대답도 "예"여야합니다.
우리는 한 문제에 대한 YES 대답은 다른 질문에 대한 YES 대답을 의미하므로 하나의 문제에 대한 NO 응답은 다른 문제에 대한 NO 응답을 의미합니다. 따라서 문제는 동일합니다. 문제의 인스턴스는 다항식 시간 및 공간에서 명확하게 구성 될 수 있습니다. 귀하의 문제는 NP 하드입니다.
"CEGH, 결합 길이." -> "CEGH, 조합 길이는 4입니다." ? –
[XY가 하나 이상의 유효한 조합의 부분 집합 인 경우] [[X가 Y에 인접]]에 의해 주어지는 객체의 무 방향성 그래프를 고려하십시오. (유효한 조합을 한 번 통과하면 그래프를 작성할 수 있습니다.) 그래프가 연결되어 있습니까? 그렇지 않은 경우 문제를 엄격하게 작은 분리 된 하위 문제로 쉽게 나눌 수 있습니다. –
연결되어있는 경우 log (1 + 객체가있는 유효한 조합 수) 및 log (1 + 유효 조합의 수는 가장자리입니다)의 가장자리 용량으로 정점 용량을 계산합니다. (contracting) (https://en.wikipedia.org/wiki/Edge_contraction#Vertex_cleaving)을 연결하고 [generalized max-flow] (https : //en.wikipedia. org/wiki/Max-flow_min-cut_theorem # Generalized_max-flow_min-cut_theorem). (이러한 용량은 유효한 조합을 통해 단 한 번만 통과하여 계산할 수 있습니다.) –