배경 : Exact-3D-Matching 문제는 다음과 같이 정의됩니다 (정의는 Jeff의 강의 노트 : 강의 29 : NP-Hard Problems 에서 가져옴). 3 차원 일치 참조) :
정확한 -3D- 매칭 : $ S $ 세트와 $ S $의 3 개 요소 하위 집합 모음 ( 트리플 )이 주어지면 $ S $를 정확히 포함하는 분리 된 트리플의 하위 모음이 있습니까? ?
3-Partition 문제는 다음과 같이 정의됩니다 (또한 강의 29 : NP-Hard 문제 . 또한 3- 파티션 문제 를 참조 할 수도 있습니다.) :
$ 3n $ 정수의 $ S $ 세트가 주어지면 $ n $ 분리 된 3 개 요소 하위 집합으로 분할하여 모든 하위 집합이 정확히 동일한 합계를 갖도록 할 수 있습니까?
3-Partition 문제는 NP 완료
문제입니다. 그리고 Exact-3D-Matching 문제의 NP- 완전성은 3SAT 문제를 줄임으로써 증명됩니다 (둘 다 컴퓨터 및 난 수성 : NP 완전성 이론 가이드 ).
문제 : 내 문제는 다음과 같습니다.
문제를
3-Partition문제로 줄였습니까?
저는 논문이나 그것에 대한 강의 노트.
댓글
답변
이 축소가 효과가있을 것 같습니다.
주어진 3-PARTITION 인스턴스 : $ n $ 정수 $ a_1, \ ldots, a_ {3n} $ 및 목표 합계 $ B $; 고유 식별자 $ \ hat {a_i} $로 각 정수를 표시합니다. 그런 다음 $ a_와 같은 3 개 요소 하위 집합 $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $ 모음을 만듭니다. {i_1} + a_ {i_2} + a_ {i_3} = B $ 및 $ i_1 \ neq i_2 \ neq i_3 $ (컬렉션에는 $ O (n ^ 3) $ 요소가 있음)
원본 3-PARTITION 문제는 $ S = \ hat {a} _ {1}, \ ldots를 포함하는 정확한 3D 일치 $ C_ {j_1}, \ ldots, C_ {j_n} $가있는 경우에만 해결책이 있습니다. , \ hat {a} _ {3n} $.
예 : $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ 빌드 : $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ 및 3 개 요소 하위 집합 모음 :
C1 = { 5a, 2a, 1a } C2 = { 5a, 2a, 1b } C3 = { 5a, 2b, 1a } C4 = { 5a, 2b, 1b } C5 = { 4a, 3a, 1a } C6 = { 4a, 3a, 1b } C7 = { 4a, 3b, 1a } C8 = { 4a, 3b, 1b } C9 = { 4a, 3c, 1a } C10 = { 4a, 3c, 1b } C11 = { 4a, 2a, 2b } C12 = { 3a, 3b, 2a } C13 = { 3a, 3b, 2b } C14 = { 3a, 3c, 2a } C15 = { 3a, 3c, 2b } C16 = { 3b, 3c, 2a } C17 = { 3b, 3c, 2b } 정확한 3D 일치는 다음과 같이 제공됩니다.
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } 또한 원래의 3-PARTITION 문제에 대한 유효한 솔루션을 고유하게 식별합니다. .
댓글
- 예, 작동합니다. 각 $ a_i $를 고유하게 표시하지 못했습니다. 감사합니다.
Exact-3D-Matching에서3-Partition로의 축소는 교과서에서 쉽게 찾을 수 있습니다 (축소 자체는 쉽지 않음). 따라서 나는 반대 방향을 요구하고 있습니다. 제목을 변경하고 답변을 수락하겠습니다.