이 질문은 다른 질문에 대한 답변으로 게시 한 답변 과 관련이 있습니다.
3- 파티션 문제는 다음과 같은 문제입니다.
인스턴스 : 양의 정수 a 1 ,…, n , 여기서 n = 3m이고 n 정수의 합은 mB와 같습니다. 따라서 각 i 는 B / 4 <a i를 충족합니다. <B / 2.
질문 : 정수 a 1 ,…, n 을 m 멀티 세트로 분할하여 각 멀티 세트의 합이 B와 같을 수 있습니까?
3- 파티션 문제는 입력의 숫자가 단항으로 제공 되더라도 NP- 완료 상태를 유지한다는 강한 의미에서 NP- 완료라는 것이 잘 알려져 있습니다. 증거는 Garey와 Johnson 을 참조하십시오 .
질문 : 숫자 a 1 ,…, n 이 모두 다른 경우 3- 파티션 문제가 NP- 완료 상태로 유지 됩니까? 강력한 의미에서 NP- 완료 상태를 유지합니까?
(제 생각에 두 질문에 대한 답은 모두 예일 것입니다. 모든 숫자가 다른 경우 문제가 더 쉬워지는 이유를 알 수 없기 때문입니다.)
Garey와 Johnson의 증거가이 제한된 버전의 NP- 완전성을 설정하는 것 같지는 않습니다.
위에 링크 된 다른 질문에 대한 답변에서, 나는 고유 한 숫자를 가진 6 파티션 문제 (유사하게 정의 됨)가 강력한 의미에서 NP- 완전하다는 증거를 제시했습니다.
답변
a1,…,an
B/4<ai<B/2
[1] : Heather Hulett, Todd G. Will, Gerhard J. Woeginger : 학위 시퀀스의 멀티 그래프 구현 : 최대화가 쉽고 최소화가 어렵습니다. 오퍼 입술 레트 사람. 36 (5) : 594-596 (2008). 도이