80년 만에 풀린 수학의 마지막 퍼즐

영화 '굿 윌 헌팅'의 실제 모델이 된 수학자 조지 댄치그가 1939년 우연히 발견한 수학적 방법론의 마지막 의문점이 해결됐습니다.

댄치그는 당시 버클리캘리포니아대(UC버클리) 대학원생으로 통계 수업에 늦게 들어가 칠판의 미해결 문제 두 개를 숙제로 착각해 풀었고, 이것이 훗날 수학사에 한 획을 그은 '단체법(simplex method)'의 시작이었습니다.

기사의 이해를 돕기 위한 자료 사진 / 영화 '굿 윌 헌팅'

지난 13일(현지 시간) 미국 과학전문매체 '콘타 매거진(Quanta Magazine)'에 따르면, 소피 휘버트 프랑스국립과학연구센터(CNRS) 연구원과 엘레온 바흐 독일 뮌헨공대 연구원이 단체법의 이론적 한계를 완전히 해결했습니다.

연구진은 단체법이 현실의 데이터처럼 약간의 불확실성이 섞인 조건에서도 '항상 다항식 시간 안에 수렴한다'는 것을 수학적으로 증명했습니다.

현실 세계를 움직이는 최적화 알고리즘

단체법은 2차 세계대전 직후 미 공군의 자원 배분 문제 해결을 위해 개발된 최적해 알고리즘입니다.

제한된 자원을 효율적으로 나누는 데 사용되며, 현재 물류, 자원 배분, 공급망 관리 등 다양한 분야에서 핵심적인 역할을 하고 있습니다.

구체적인 예를 들면, 한 공장이 전력, 인력, 원재료라는 세 가지 자원으로 세 종류의 제품을 생산한다고 가정해봅시다.

기사의 이해를 돕기 위한 AI 이미지 / google ImageFx

전력 사용량과 인력 투입 시간에는 한계가 있고, 각 제품의 단위당 수익도 서로 다릅니다.

이때 공장은 "제한된 자원 안에서 총이익을 최대화하는 생산 조합"을 찾아야 합니다.

단체법은 이러한 복잡한 문제를 입체 공간의 평면과 꼭짓점으로 시각화하고, 가장 높은 이익이 예상되는 꼭짓점을 향해 단계적으로 이동하며 최적 해를 도출합니다.

이 단순한 원리가 오늘날 전 세계 물류, 에너지, 금융, AI 학습 최적화에 이르기까지 광범위하게 활용되고 있습니다.

80년간 지속된 이론적 논란의 종료

그러나 단체법에는 치명적인 이론적 약점이 있었습니다.

1970년대 이후 수학자들은 최악의 경우 변수 개수에 따라 계산 시간이 '2ⁿ'인 지수 수준으로 폭증할 수 있다는 '지수적 복잡도' 문제를 지적해왔습니다.

이론적으로는 알고리즘이 끝없이 돌아갈 수도 있다는 우려였습니다.

기사의 이해를 돕기 위한 AI 이미지 / google ImageFx

이 문제에 대한 첫 번째 돌파구는 2001년 대니얼 슈필먼 예일대 교수와 상화 텡 남가주대 교수가 마련했습니다.

두 연구자는 알고리즘에 무작위성을 도입하면 '지수적 지연'을 피할 수 있다는 사실을 발견했습니다.

휘버트 연구원과 바흐 연구원은 이 개념을 한 단계 더 발전시켰습니다.

연구진은 단체법이 현실의 데이터처럼 약간의 불확실성이 섞인 조건에서도 계산 시간이 끝없이 늘어나지 않고 가장 효율적인 속도로 문제를 해결할 수 있다는 것을 수학적으로 완벽하게 입증했습니다.

하이코 뢰글린 독일 본대 교수는 콴타 매거진과의 인터뷰에서 "단체법의 실질적 효율성을 수학적으로 완벽히 설명한 첫 연구"라고 이번 성과를 평가했습니다. 이번 연구 결과는 오는 12월 호주에서 열리는 '컴퓨터과학기초심포지엄(FOCS)'에서 공식 발표될 예정입니다.

휘버트 연구원은 "단체법은 80년 동안 잘 작동했지만 그 이유를 이해한 건 이제서야"라며 "다음 목표는 제약 조건 개수에 선형으로 비례하는 알고리즘을 찾는 것"이라고 향후 연구 방향을 밝혔습니다.