이 질문은 다른 질문에 대한 답변으로 게시 한 답변 과 관련이 있습니다.

3- 파티션 문제는 다음과 같은 문제입니다.
인스턴스 : 양의 정수 a ₁ ,…, _n , 여기서 n = 3m이고 n 정수의 합은 mB와 같습니다. 따라서 각 _i 는 B / 4 <a _i를 충족합니다. <B / 2.
질문 : 정수 a ₁ ,…, _n 을 m 멀티 세트로 분할하여 각 멀티 세트의 합이 B와 같을 수 있습니까?

3- 파티션 문제는 입력의 숫자가 단항으로 제공 되더라도 NP- 완료 상태를 유지한다는 강한 의미에서 NP- 완료라는 것이 잘 알려져 있습니다. 증거는 Garey와 Johnson 을 참조하십시오 .

질문 : 숫자 a ₁ ,…, _n 이 모두 다른 경우 3- 파티션 문제가 NP- 완료 상태로 유지 됩니까? 강력한 의미에서 NP- 완료 상태를 유지합니까?

(제 생각에 두 질문에 대한 답은 모두 예일 것입니다. 모든 숫자가 다른 경우 문제가 더 쉬워지는 이유를 알 수 없기 때문입니다.)

Garey와 Johnson의 증거가이 제한된 버전의 NP- 완전성을 설정하는 것 같지는 않습니다.

위에 링크 된 다른 질문에 대한 답변에서, 나는 고유 한 숫자를 가진 6 파티션 문제 (유사하게 정의 됨)가 강력한 의미에서 NP- 완전하다는 증거를 제시했습니다.

답변