OpenAI의 '역대급' 알고리즘, 우주보다 큰 숫자에서만 빨라진다
Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
복잡도 이론은 1965년 Jack Edmonds가 '효율적' 알고리즘을 다항 시간으로 정의하면서 시작됐다. 하지만 이 정의는 n^1000 같은 터무니없는 경우를 낳았고, 최근 OpenAI가 발표한 satisfiability 문제의 '서브지수 시간' 알고리즘도 변수가 10^10,000,000,000,000,000,000,000,000개 미만이면 사실상 전수 탐색을 한다. 우주의 원자 수(10^80)보다도 압도적으로 큰 수다. 결국 이 결과는 효율성에 대해 아무것도 말해주지 않는다.
내가 베팅하는 사람은 아니지만, 예측 하나는 있다. 어떤 '은하적' 의미에서 P=NP가 성립할 것이고, 우리가 배우게 될 것은 지난 50년 동안 잘못된 질문에 답해왔다는 사실뿐일 것이다.