분할 문제

분할 문제(partition problem)는 전산학에서 다루는 NP-완전 문제이다. 이 문제는 정수 중복집합을 합이 같은 두 집합으로 나눌 수 있는지를 묻는다. 더 정확히 기술하면, 정수 중복집합 S가 있을 때, S를 S₁과 S₂로 나누어서 두 부분집합에 속한 숫자들의 합이 똑같도록 할 수 있는지를 묻는 문제이다. 부분집합 S₁과 S₂는 서로소이고 S를 덮는다는 관점에서 볼 때 S를 분할한다.

분할 문제는 부분집합 합 문제의 특수한 경우와 동치이다. 정수 집합 S가 있고 S의 모든 원소의 합이 t일 때, 원소의 합이 t/2가 되는 부분집합 S₁이 있는지를 묻는 것이다. (S − S₁을 찾는 것도 이와 동치이다.) 그러므로 부분집합 합 문제에 대한 의사 다항 시간 동적계획법이 분할 문제에도 잘 작동한다.

분할 문제의 변형으로 3분할 문제가 있다. 집합 S를 원소의 합이 |S|/3 인 세 부분집합으로 나누는 문제이다. 분할 문제와 달리 3분할 문제를 푸는 의사 다항 시간 알고리즘은 P = NP가 아닌 한 존재하지 않는다. 즉, 3분할 문제는 일진 코딩을 쓰는 경우에도 NP-완전이다.

더 보기

• 부분집합 합 문제
• 상자 채우기 문제