알고리즘 효율성의 정의를 놓친 50년, 이론과 현실의 단절
Key Point
컴퓨터과학 기초 이론이 현실의 계산 능력과 완전히 단절되어 있으며, 세계적 기업이 발표한 '획기적' 결과도 실제로는 구현 불가능한 매개변수를 감추고 있다는 점을 보여주기 때문입니다.
핵심 요약
- 1965년 잭 에드몬즈가 그래프 최대 매칭 알고리즘을 발표할 때 '효율성'의 명확한 정의가 없었고, 2페이지를 할애해 지수 시간은 나쁘고 다항식 시간은 좋다는 기준을 처음 제안했다.
- 에드몬즈는 자신의 기준이 불완전함을 알았고, n^1000 같은 다항식도 현실에서는 효율적이지 않으며 일부 지수 알고리즘(심플렉스)이 실무에서 빠르게 작동한다는 점을 이미 지적했다.
- 이 모호한 정의로 50년간 복잡도 이론이 발전했고, 현재 우리에게는 '복잡도 동물원'이라는 표현할 수 없을 정도로 큰 실행 시간을 가진 '우주적 알고리즘(galactic algorithm)'들이 쌓여 있다.