PARTITION에서 SUBSET SUM까지의 Karp 감소

Question

PARTITION : 양의 정수 집합 A = {a_1, ..., a_n}에서 A의 보수가 합계와 같은 부분 집합이 있습니까?

SUBSET SUM : 양의 정수 A = {a_1, ..., a_n}과 다른 양의 정수 B가 주어지면 그 합이 B와 같도록 A의 하위 집합이 존재합니까?

PARTITION이 NP-complete이면 SUBSET SUM도 PART를 SSUM으로 줄임으로써 NP 완성이라는 것을 증명하려고했습니다.

내 해결책은 다음과 같습니다. A = {a1, ..., an}을 양의 정수 집합이라고합시다. 그런 다음 A가 PART로 공급되면 I = {k1, ..., km} (k_i는 해의 부분 집합의 구성원의 색인) 솔루션을 제공하면 A '= {a1, ... an, S} 여기서 S는 {a_k1, a_k2, ..., a_km}의 합계입니다. A '는 SSUM에 대한 해결책입니다.

내 문제는 이것이 한 방향으로 만 진행된다는 것입니다. 즉, 주어진 A ', 그 다음 A가 PART에 대한 해결책임을 보여줄 수 없다는 것입니다. 이게 문제 야? 어떻게 그것을 감당할 수 있을까요?

Answer 1

SubsetSum으로 파티션하는 것은 실제로 여기에서했던 것보다 쉽습니다.

파티션이 만족되면 합계 (P1) = 합계 (P2)가 올바른 일부 서브 세트 P1과 P2가 있음을 의미합니까? (P1) = 합 (P2) = (1/2) 합 (A)

우리는 서브 세트 합계에 대한 A '. A '= A와 목표 합계 = (1/2) 합계 (A)로 설정하면됩니다. 이것이 추상화가 거의없는 파티션과 완전히 동일한 문제임이 분명해야합니다.

즉, Partion은 항상 target sum = (1/2) sum (A)

인 부분 집합 합계입니다.