분할 문제

3. 계산 복잡도

분할 문제는 NP-난해(NP-hard)이다. 이는 부분 집합 합 문제로부터의 환원을 통해 증명할 수 있다.^[4] 부분 집합 합 문제의 예시는 양의 정수 집합 ''S''와 목표 합 ''T''로 구성되며, 목표는 ''S''의 부분 집합 중 합이 정확히 ''T''가 되는 것이 있는지 결정하는 것이다.

이러한 예시가 주어지면, 입력 집합이 원래 집합과 두 개의 원소인 ''z''₁과 ''z''₂를 포함하는 분할 문제의 예시를 구성한다. 여기서 ''z''₁ = sum(S)이고, ''z''₂ = 2''T''이다. 이 입력 집합의 합은 sum(''S'') + ''z''₁ + ''z''₂ = 2 sum(''S'') + 2''T''이므로, 분할 문제의 목표 합은 sum(''S'') + ''T''이다.

• 부분 집합 합 문제의 인스턴스에 대한 해 ''S''′이 존재한다고 가정하자. 그러면 sum(''S''′) = ''T''이므로, sum(S′ ∪ ''z''₁) = sum(''S'') + ''T''이며, 따라서 ''S''′ ∪ ''z''₁은 분할 문제의 해이다.
• 반대로, 분할 문제의 인스턴스에 대한 해 ''S''′′이 존재한다고 가정하자. 그러면 ''S''′′은 ''z''₁ 또는 ''z''₂ 중 하나를 포함해야 하지만, 둘 다 포함할 수는 없다. 왜냐하면 두 값의 합이 sum(''S'') + ''T''보다 크기 때문이다. 만약 S''가 ''z''₁을 포함한다면, 정확히 ''T''의 합을 갖는 ''S''의 원소들을 포함해야 하며, 따라서 S''에서 ''z''₁을 뺀 것이 부분 집합 합 문제의 해이다. 만약 S''가 ''z''₂를 포함한다면, 정확히 sum(''S'') - ''T''의 합을 갖는 S의 원소들을 포함해야 하며, 따라서 ''S''의 다른 객체들이 부분 집합 합 문제의 해이다.

4. 근사 알고리즘

• '''탐욕적 숫자 분할''' - 숫자를 반복하면서 각 숫자를 현재 합이 가장 작은 집합에 넣는다. 숫자가 정렬되지 않은 경우, 실행 시간은 O(''n'')이고 근사 비율은 최대 '''3/2'''이다. 숫자를 정렬하면 실행 시간이 O(''n'' log ''n'')으로 증가하고 근사 비율이 '''7/6'''으로 향상된다. 숫자가 [0,1]에서 균일하게 분포된 경우, 근사 비율은 $1\; +\; O\backslash left(\backslash frac\{\backslash log\backslash log\; n\}\{n\}\backslash right)$ 거의 확실하게 최대이고, 기대값은 $1\; +\; O\backslash left(\backslash frac\{1\}\{n\}\backslash right)$이다.
• '''최대 차이 방법''' ('''Karmarkar–Karp 알고리즘''이라고도 함)은 숫자를 내림차순으로 정렬하고 숫자를 반복적으로 차이로 대체한다. 실행 시간 복잡도는 O(''n'' log ''n'')이다. 최악의 경우, 근사 비율도 비슷하며 최대 '''7/6'''이다. 그러나 평균적인 경우 탐욕 알고리즘보다 훨씬 더 나은 성능을 보입니다. 숫자가 [0,1]에서 균일하게 분포된 경우, 기대값에서 근사 비율은 $1\; +\; 1/n^\{\backslash Theta(\backslash log\; n)\}$이다. 또한 시뮬레이션 실험에서도 더 나은 성능을 보입니다.
• '''multifit 알고리즘'''은 빈 포장에 대한 알고리즘과 결합된 이진 검색을 사용한다. 최악의 경우, 근사 비율은 '''8/7'''이다.
• 부분 집합 합 문제에는 목표 합을 sum(''S'')/2로 설정하여 분할 문제에도 사용할 수 있는 '''FPTAS'''가 있다.

5. 정확한 알고리즘

• 유사 다항 시간 숫자 분할은 m이 입력에서 가장 큰 숫자일 때, $O(n\; m)$ 메모리를 사용한다.
• '''완전 탐욕 알고리즘(CGA)'''은 이진 트리를 구성하여 모든 분할을 고려한다. 트리의 각 레벨은 입력 숫자에 해당하며, 루트는 가장 큰 숫자에 해당하고, 그 아래 레벨은 다음으로 큰 숫자에 해당한다. 각 분기는 현재 숫자를 넣을 수 있는 다른 집합에 해당한다. 트리를 깊이 우선 순서로 탐색하는 데에는 $O(n)$ 공간만 필요하지만, $O(2^n)$ 시간이 걸릴 수 있다. 각 레벨에서, 현재 숫자가 합이 가장 작은 집합에 놓이는 분기를 먼저 개발하여 실행 시간을 개선할 수 있다. 이 알고리즘은 탐욕 숫자 분할에 의해 처음 발견된 해를 찾은 다음, 더 나은 해를 찾기 위해 진행한다.^[5][6]
• '''완전 카르마르카–카르프 알고리즘(CKK)'''는 이진 트리를 구성하여 모든 분할을 고려한다. 각 레벨은 두 개의 숫자에 해당한다. 왼쪽 분기는 서로 다른 부분 집합에 넣는 것(즉, 차이로 대체)에 해당하고, 오른쪽 분기는 동일한 부분 집합에 넣는 것(즉, 합으로 대체)에 해당한다. 이 알고리즘은 먼저 최대 차분법에 의해 발견된 해를 찾은 다음, 더 나은 해를 찾기 위해 진행한다. 무작위 인스턴스에서 CGA보다 상당히 빠르게 실행된다. 특히 동일한 분할이 존재하는 경우 이점은 훨씬 더 크며, 여러 자릿수가 될 수 있다. 실제로, 숫자가 최대 12개의 유효 숫자를 가지는 경우, 임의의 크기의 문제를 CKK로 해결할 수 있다.^[7]
• 부분 집합 합 문제를 위해 개발된 알고리즘은 다음과 같다.
• '''Horowitz and Sanhi''' – O(\; 2^\{n/2\}\backslash cdot\; (n/2)) 시간에 실행되지만 O(\; 2^\{n/2\}) 공간이 필요하다.
• '''Schroeppel and Shamir''' – O(\; 2^\{n/2\}\backslash cdot\; (n/4)) 시간에 실행되며, 훨씬 적은 공간 $O(2^\{n/4\})$이 필요하다.
• '''Howgrave-Graham and Joux''' – $O(2^\{n/3\})$ 시간에 실행되지만, 결정 문제만 해결하는 무작위 알고리즘이다(최적화 문제가 아님).

6. 난해한 인스턴스와 상전이

하나 또는 0개의 분할만 있는 집합은 입력 크기에 비해 해결하기가 가장 어렵거나 비용이 많이 드는 경향이 있다. 값이 집합의 크기에 비해 작으면 완전 분할이 더 가능성이 높다. 이 문제는 "상 전이"를 겪는 것으로 알려져 있는데, 일부 집합에서는 가능성이 높고 다른 집합에서는 가능성이 낮다. 집합의 임의의 숫자를 표현하는 데 필요한 비트 수가 m이고 집합의 크기가 n인 경우 m/n < 1이면 많은 해를 가지는 경향이 있고 m/n > 1이면 해가 거의 없거나 없는 경향이 있다. n과 m이 커질수록 완전 분할의 확률은 각각 1 또는 0에 접근한다. 이는 원래 젠트와 월시에 의해 경험적 증거를 기반으로 주장되었으며, 이후 머튼스에 의해 통계 물리학의 방법을 사용하여, 나중에 보르그스, 체이스, 피텔에 의해 증명되었다.

7. 확률적 버전

생일 문제와 유사하게, 입력 집합의 크기를 결정하는 문제가 있다. 입력 집합의 각 요소가 1에서 특정 값 사이에서 균일 분포로 무작위로 선택된다는 가정 하에, 해가 존재할 확률이 1/2가 되도록 하는 것이다. 이 문제의 해는 생일 문제와 마찬가지로 직관에 반하는 결과를 보일 수 있다.

8. 변형 및 일반화

'''동수 분할'''은 두 부분 집합의 원소 개수가 같아야 한다는 제약 조건이 추가된 분할 문제의 변형이며, 합도 같아야 한다. 이 변형 역시 NP-hard 문제이다.^[3] 표준 분할 문제의 인스턴스에 임의의 숫자 ''n''개가 주어졌을 때, ''n''개의 0을 추가하여 동수 분할 문제의 인스턴스를 구성한다. 분명히, 새로운 인스턴스가 동수 합을 갖는 동수 분할을 갖는 것은 원래의 인스턴스가 동수 합 분할을 갖는 것과 같다. 균형 숫자 분할도 참조하라.

'''곱 분할'''은 정수 집합을 합이 아닌 같은 ''곱''을 갖는 두 개의 집합으로 분할하는 문제이다. 이 문제는 강한 NP-완전성을 갖는다.^[8]

코발료프(Kovalyov)와 페쉬(Pesch)^[9]는 분할 유형 문제의 NP-hardness를 증명하는 일반적인 접근 방식을 논의한다.

9. 응용

분할 문제는 선거 조작에 응용될 수 있다. 예를 들어 A, B, C 세 후보가 있고, 거부권 규칙(각 유권자는 단일 후보를 거부하고, 거부표가 가장 적은 후보가 승리)을 통해 한 명을 뽑는다고 가정하자. 만약 특정 연합이 C의 당선을 보장하려면, A와 B에게 표를 분배하여 각각 받는 거부표 수를 최소화해야 한다. 투표에 가중치가 있다면, 이 문제는 분할 문제로 축소되며, CKK를 사용하여 효율적으로 해결할 수 있다. 이는 점수 기반의 다른 모든 투표 규칙에도 마찬가지로 적용된다.^[10]

참조

_[1] 간행물 The Easiest Hard Problem http://bit-player.or[...] Sigma Xi, The Scientific Research Society 2002-03
_[2] conference Multi-Way Number Partitioning http://ijcai.org/pap[...]
_[3] 서적 Computers and Intractability; A Guide to the Theory of NP-Completeness https://archive.org/[...]
_[4] 웹사이트 More NP complete and NP hard problems https://www.ics.uci.[...]
_[5] 서적 Knapsack problems https://books.google[...] Springer
_[6] 서적 Knapsack problems: Algorithms and computer interpretations Wiley-Interscience
_[7] conference From approximate to optimal solutions: a case study of number partitioning https://dl.acm.org/d[...] Morgan Kaufmann Publishers 1995-08-20
_[8] 논문 "Product Partition" and related problems of scheduling and systems reliability: Computational complexity and approximation http://www.sciencedi[...] 2010-12-01
_[9] 논문 A generic approach to proving NP-hardness of partition type problems 2010-10-28
_[10] conference Where Are the Really Hard Manipulation Problems? The Phase Transition in Manipulating the Veto Rule https://www.ijcai.or[...] Morgan Kaufmann Publishers Inc. 2021-10-05