서로 다른 취향과 지식을 가진 12명의 친구들이 퀴즈 대회를 위해 실력이 팽팽한 두 팀으로 나뉘려고 합니다. 장 씨는 역사와 지리에 밝고, 이 씨는 대중음악과 영화에 익숙하며, 왕 씨는 스포츠와 요리에 능숙합니다. 모든 분야에서 두 팀이 균형을 이루도록 팀을 짜려 하면 프로세스는 금세 난관에 부딪힙니다. 역사 점수를 맞추기 위해 장 씨를 A팀으로 옮기면, A팀의 지리 전력이 순식간에 과도해지면서 지리 영역에서 두 팀의 균형이 다시 깨지고 맙니다.
겉보기에는 평범한 팀 짜기 곤란처럼 보이는 이 문제는 수학에서 ‘조합 편차 이론(combinatorial discrepancy theory: 다양한 특징을 가진 대상을 두 그룹으로 나누고 두 그룹 간의 차이를 최소화하는 수학적 연구 분야)‘에 해당합니다. 중고차 거래에서 두 대리점에 다양한 차종과 색상을 균등하게 배분하든, 임상 시험에서 환자를 치료군과 플라세보군으로 고르게 나누든, 다차원 속성이 개입하는 그룹 분배는 속성의 수가 늘어날수록 난이도가 폭발적으로 증가합니다.
수년간 수학자들은 이러한 그룹 분배 불균형의 이론적 한계를 탐구해 왔습니다. 2025년 가을, 컴퓨터 과학자 니킬 반살(Nikhil Bansal)과 하오톈 지앙(Haotian Jiang)은 새로운 알고리즘을 제안하여 30년 가까이 깨지지 않던 불균형도 상한선을 대폭 낮추었습니다. 이 연구는 엄청난 수의 특징과 거대한 집단에 직면하더라도 완벽에 가까운 균등 배분이 가능하다는 점을 증명했습니다.
공정한 그룹 나누기가 수학자들을 수십 년간 괴롭힌 이유
일상생활에서 단일 속성을 가진 대상을 나누는 것은 매우 쉽습니다. 동일한 크기의 케이크 100개가 있다면, 각각 50개씩 두 덩이로 나누면 완벽한 균형을 이룹니다. 하지만 현실에서 나눌 대상은 흔히 여러 가지 속성이 동시에 겹쳐 있습니다.
중고차 대리점 배분 상황을 예로 들면, 도매로 판매되는 차량은 보디 색상도 다르고 차종과 주행거리도 다릅니다. 단순히 전체 수량으로만 반으로 나누면, 한 매장에는 컨버터블 차량 대부분이 들어가고 다른 매장에는 빨간색 세단 대부분이 들어가는 상황이 벌어질 수 있습니다. 두 대리점 모두 모든 지표가 비슷하기를 바라지만, 각 속성이 배분안을 서로 다른 방향으로 잡아당깁니다.
의학 임상 시험에서는 이러한 상호작용이 더욱 긴밀합니다. 연구진은 피험자를 치료군과 대조군으로 나눌 때 나이 분포를 비슷하게 맞춰야 할 뿐만 아니라 혈압, 지병, 생활 습관의 비율도 고르게 만들어야 합니다. 어느 한 차원에서라도 심각한 불균형이 발생하면 임상 데이터 전체의 설득력이 떨어질 수 있습니다. 이처럼 얽히고설킨 특징 속성들은 수학자들의 눈에 매우 까다로운 ‘판 위의 줄다리기’를 만들어 냅니다.
무모하다며 자조했던 한 수학적 추측
이러한 분배의 한계를 이론적으로 규명하기 위해 헝가리의 수학자 야노시 콤로시(János Komlós)는 1980년대 초 유명한 ‘콤로시 추측(Komlós conjecture)‘을 제안했습니다. 그는 분배할 대상이 아무리 많고 각 대상에 얼마나 많은 특징 차원이 포함되어 있든 상관없이, 모든 특징에서 두 그룹 간의 최대 수치 차이(즉 편차, discrepancy: 그룹 분배 후 특정 속성에서 나타나는 두 팀의 수치 격차)가 하나의 고정된 상수를 넘지 않는 분배안을 항상 찾을 수 있다고 추측했습니다.
콤로시 본인은 훗날 자신이 당시 젊고 무모했기 때문에 이런 추측을 제안할 수 있었다고 농담조로 말하곤 했습니다. 당시에는 유용한 수학적 도구가 부족했기 때문에 대상의 수에 따라 증가하지 않는 고정된 상수 상한을 증명하는 것이 극도로 어려웠으며, 그는 심지어 이 제안을 ‘무책임한 추측’이라고 부르기까지 했습니다.
이후 수십 년 동안 학계 전체는 긴 릴레이 레이스를 펼쳤습니다. 1985년 수학자 조엘 스펜서(Joel Spencer)는 편차가 대상의 수 N의 로그 값인 log N 이내로 제어될 수 있음을 증명했고, 1998년 보이치에흐 바나슈치크(Wojciech Banaszczyk)는 상한을 log N의 제곱근으로 개선했습니다. 하지만 그 이후 수학계는 이 기록 앞에서 30년 가까이 정체되었으며, 많은 학자들은 이 한계를 더 이상 깨뜨릴 수 없을 것이라 의심하기도 했습니다.
일주일간의 방문이 가져온 알고리즘의 돌파구
반전은 2025년 2월에 일어났습니다. 당시 워싱턴 대학교 박사과정에 재학 중이었으며 현재 시카고 대학교에 재직 중인 하오톈 지앙은 미시간 대학교 앤아버 캠퍼스를 방문하여 컴퓨터 과학자 니킬 반살을 만났습니다. 반살은 이미 2010년에 개별 대상을 분할한 뒤 무작위 교란을 거쳐 재조합하는 알고리즘을 설계하여 스펜서의 기록과 어깨를 나란히 한 바 있었습니다.
지앙이 방문한 둘째 날, 두 사람은 토론 중 새로운 돌파구를 발견했습니다. 반년에 걸친 추론과 보완 끝에 그들은 2025년 가을 새 알고리즘을 공식 발표했으며, 그룹 간 최대 편차의 상한을 log(N)의 4제곱근까지 끌어내렸습니다. 이는 근 30년 만에 인류가 해당 분야의 이론적 정체를 깨뜨린 사건이었습니다.
그림: 벡터 줄다리기와 균등 배분의 수학적 개념도. 출처: Quanta Magazine / Ada Zejun Shen
그림: Komlós 추측을 돌파한 두 연구자 Haotian Jiang(왼쪽)과 Nikhil Bansal(오른쪽). 출처: Quanta Magazine / Emily France, University of Michigan
복잡하게 얽힌 속성들이 서로 방해하지 않도록 만드는 법
기존의 분배 알고리즘은 처리 과정에서 전체적인 불균형도의 최종 누적값에만 집중하는 경향이 있었습니다. 속성의 수가 늘어나면 하나의 속성에 가해진 조작이 나비효과처럼 작동하여 다른 속성의 균형을 격렬하게 방해하곤 했습니다.
반살과 지앙의 새로운 방법은 ‘의존성(dependency)‘에 대한 정밀한 측정 메커니즘을 도입했습니다. 그들은 한 속성을 무작위로 교란할 때 다른 속성의 편차가 어느 정도의 연동 변화를 일으키는지 평가하는 시스템을 설계했습니다.
계산 과정에서 속성 간의 무작위 간섭을 차단함으로써, 알고리즘은 각 차원이 서로 방해받지 않고 독립적으로 미세 조정을 수행하도록 만드는 데 성공했습니다. 이러한 구조는 이론적 상한을 4제곱근으로 낮추었을 뿐만 아니라, 실제 컴퓨터 연산에서 합리적인 시간 내에 결과를 계산해 낼 수 있는 효율적 알고리즘(efficient algorithm)을 제공하여 실전 계산에 직접 적용할 수 있게 했습니다.
온 우주의 원자를 나누어도 차이는 겨우 3
log N의 4제곱근이라는 식은 수학 공식으로 볼 때는 다소 추상적으로 느껴질 수 있지만, 이를 현실의 스케일에 적용해 보면 성과의 직관적인 영향력이 명확히 드러납니다.
분배 대상의 수 N = 10일 때, 로그 4제곱근의 값은 대략 1과 같습니다. 만약 분배 대상의 수를 관측 가능한 우주에 존재하는 모든 원자의 추정 총수—약 10^81 개(1 뒤에 0이 81개 붙는 수)—까지 늘리더라도, 이 공식으로 계산한 최대 편차 값은 겨우 3 정도로만 증가합니다.
예일 대학교의 수학자 대니얼 스필먼(Daniel Spielman)은 이에 대해 “인류의 생애 동안 로그 4제곱근 값이 5를 넘는 숫자를 보는 것은 거의 불가능할 것”이라고 평가했습니다. 이는 데이터 규모가 천문학적인 수준으로 확대되더라도 그룹 불균형의 정도는 거의 정지 상태를 유지하며 상수에 무한히 가까워진다는 것을 의미합니다.
토론토 대학교 연구원 알렉산다르 니콜로프(Aleksandar Nikolov)는 과거에 콤로시 추측이 성립하지 않을 것이라 생각하는 편이었으나, 이번 성과를 보고 추측이 참일 확률이 극도로 높다고 다시 확신하게 되었다고 털어놓았습니다. 헝가리 레니 연구소의 연구원 레이니 헤크(Rainie Heck) 역시 이 이론이 대형 언어 모델과 머신러닝 시스템의 최적화에 도입되고 있으며, 머지않아 누군가 상수 경계의 존재를 완전히 증명할 가능성이 높다고 지적했습니다.
완벽에 가까운 공정함이 눈앞에 다가오다
무수히 복잡한 속성을 가진 대상들을 오차 제로의 절대적인 공정함으로 나누는 일에는 수학적 법칙상 언제나 한계가 존재합니다. 하지만 반살과 지앙의 돌파구는 완벽에 가까운 균형이 이론적으로 완전히 가능할 뿐만 아니라 컴퓨터를 통해 효율적으로 실현될 수 있음을 세상에 증명해 보였습니다.
40년 전 무모해 보였던 수학적 추측에서 시작하여 30년 동안 난공불락이었던 제곱근의 벽에 이르기까지, 수학자들은 불균형도의 이론적 한계를 차근차근 허물어 왔습니다. 그들은 정교한 알고리즘을 통해 아무리 복잡하고 혼란스러운 세상일지라도 인류에게는 혼돈을 질서로 돌려놓을 강력한 지혜가 있음을 입증해 낸 것입니다.
참고 링크:
- Quanta Magazine 보도
