알고리즘 효율성의 정의를 놓친 50년, 이론과 현실의 단절
원제 Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
102 포인트댓글 80
Key Point
컴퓨터과학 기초 이론이 현실의 계산 능력과 완전히 단절되어 있으며, 세계적 기업이 발표한 '획기적' 결과도 실제로는 구현 불가능한 매개변수를 감추고 있다는 점을 보여주기 때문입니다.
핵심 요약
- 1965년 잭 에드몬즈가 그래프 최대 매칭 알고리즘을 발표할 때 '효율성'의 명확한 정의가 없었고, 2페이지를 할애해 지수 시간은 나쁘고 다항식 시간은 좋다는 기준을 처음 제안했다.
- 에드몬즈는 자신의 기준이 불완전함을 알았고, n^1000 같은 다항식도 현실에서는 효율적이지 않으며 일부 지수 알고리즘(심플렉스)이 실무에서 빠르게 작동한다는 점을 이미 지적했다.
- 이 모호한 정의로 50년간 복잡도 이론이 발전했고, 현재 우리에게는 '복잡도 동물원'이라는 표현할 수 없을 정도로 큰 실행 시간을 가진 '우주적 알고리즘(galactic algorithm)'들이 쌓여 있다.
- 최근 OpenAI가 충족 가능성 문제(satisfiability)를 준지수 시간에 푸는 알고리즘을 '이론 전산학 50년 최대 성과'라며 발표했으나, 실제로는 변수 개수가 10^10000000000000000000000000 미만일 때만 이 성능을 보인다.
- 우주의 원자 개수(약 10^80)와 비교하면 이 임계값은 1조 조 배 이상 크므로, 현실에서 다룰 수 있는 모든 문제에서는 지수 시간 알고리즘을 호출한다.
- 저자는 이 사례가 '효율성'의 정의가 50년 전보다도 더 잘못되었음을 증명하며, 응용 수학에서 원래 풀 문제를 잊고 수학적 퍼즐 해결에만 빠지는 전형적인 패턴을 보여준다고 지적한다.