영화 ‘굿 윌 헌팅’에는 미국 매사추세츠공과대(MIT)에서 청소부로 일하던 주인공이 복도 칠판에 적힌 어려운 수학 문제를 풀어 교수들을 놀라게 한다.
이 장면은 실화를 바탕으로 했다. 실제 주인공은 미국 수학자 조지 댄치그다. 1939년 미국 버클리캘리포니아대(UC버클리) 대학원 시절 통계 수업에 늦게 들어가 칠판에 적힌 미해결 문제 두 개를 숙제로 착각해 풀었다. 그때의 ‘문제’가 훗날 수학사에 한 획을 그은 ‘단체법(simplex method)’으로 이어졌다.
그로부터 80여 년이 지난 지금 댄치그가 만든 이 수학적 방법의 마지막 의문이 풀렸다.
댄치그가 고안한 단체법은 물류, 자원 배분, 공급망 등에서 제한된 자원을 효율적으로 나누는 데 널리 쓰이는 최적해를 구하는 알고리즘이다. 하지만 이론적으로는 계산 시간이 무한히 길어질 수 있다는 ‘지수적 복잡도’ 논란이 불거졌다.
13일(현지시각) 미국 과학전문매체 ‘콴타 매거진(Quanta Magazine)’ 보도에 따르면 소피 휘버트 프랑스국립과학연구센터(CNRS) 연구원과 엘레온 바흐 독일 뮌헨공대 연구원은 단체법이 현실의 데이터처럼 약간의 불확실성이 섞인 조건에서도 ‘항상 다항식 시간 안에 수렴한다’는 것을 증명했다. 이번 결과는 오는 12월 호주에서 열리는 ‘컴퓨터과학기초심포지엄(FOCS)’에서 공식 발표될 예정이다.
● 무작위성이 효율성 만든다
단체법은 2차 세계대전 직후 미 공군의 자원 배분 문제를 해결하기 위해 만들어졌다.
예를 들어 한 공장이 전력, 인력, 원재료 세 자원을 써서 세 종류의 제품을 만든다고 하자. 전력 사용량과 인력 투입 시간에는 한도가 있고 각 제품의 단위당 수익도 다르다. 공장은 “제한된 자원 안에서 총이익을 최대화하는 생산 조합”을 찾아야 한다.
단체법은 이 문제를 입체 공간의 평면과 꼭짓점으로 표현하고 가장 높은 이익이 예상되는 꼭짓점을 향해 단계적으로 이동하며 최적 해를 찾는다. 이 단순한 원리가 오늘날 전 세계 물류, 에너지, 금융, AI 학습 최적화에 이르기까지 다양하게 쓰이고 있다.
문제는 이 알고리즘이 이론적으로는 끝없이 돌아갈 수도 있다는 점이었다. 1970년대 이후 수학자들은 최악의 경우 변수 개수에 따라 계산 시간이 ‘2ⁿ’인 지수 수준으로 폭증할 수 있다는 이론적 한계를 지적해 왔다.
이를 해결한 것이 2001년 대니얼 슈필먼 예일대 교수와 상화 텡 남가주대 교수다. 둘은 알고리즘에 무작위성을 도입하면 이런 ‘지수적 지연’을 피할 수 있다는 사실을 밝혀냈다.
휘버트 연구원과 바흐 연구원은 이 개념을 발전시켜 단체법이 현실의 데이터처럼 약간의 불확실성이 섞인 조건에서도 계산 시간이 끝없이 늘어나지 않고 가장 효율적인 속도로 문제를 풀어낼 수 있다는 사실을 증명했다.
하이코 뢰글린 독일 본대교수는 콴타 매거진과의 인터뷰에서 “단체법의 실질적 효율성을 수학적으로 완벽히 설명한 첫 연구”라고 평가했다.
휘버트 연구원은 “단체법은 80년 동안 잘 작동했지만 그 이유를 이해한 건 이제서야”라며 “다음 목표는 제약 조건 개수에 선형으로 비례하는 알고리즘을 찾는 것”이라고 말했다.
<참고자료>
- doi.org/10.48550/arXiv.2504.04197
