알고리즘이 '효율적'이라는 말은 실무에서 늘 쓰지만, 그것을 수학적으로 엄밀하게 정의하려 하면 생각보다 금세 막힌다. 이 문제의 역사를 되짚어 보면 오늘날 복잡도 이론이 왜 현실의 계산과 종종 어긋나는지, 그리고 이번 주 화제가 된 OpenAI의 '준지수 시간' SAT 알고리즘을 어떻게 받아들여야 하는지가 함께 보인다.
'좋은 알고리즘'을 정의하려 한 1965년의 고민
출발점은 1965년 잭 에드먼즈(Jack Edmonds)다. 그는 그래프에서 최대 매칭을 찾는 영리한 절차를 고안했고, 이 알고리즘이 '효율적'으로 계산될 수 있음을 주장하고 싶었다. 그런데 막상 효율을 기술할 언어가 없었다. 논문의 'Digression(여담)'이라는 절에서 그는 사전적 의미의 '효율적(adequate in operation or performance)'을 언급하며 차라리 '좋은(good)' 알고리즘이라는 표현을 제안한다. 가능한 모든 매칭을 나열해 가장 큰 것을 고르는 방식은 분명 정답을 주지만, 매칭의 수가 그래프 크기에 대해 지수적으로 커지므로 '나쁜' 알고리즘이다. 그의 새 절차는 그보다 훨씬 나았다.
에드먼즈는 두 페이지에 걸쳐 '좋음'을 정의하려 했다. 먼저 문제 크기에 모두가 동의해야 한다고 보고, 매칭 문제에서는 정점 수와 간선 수의 합을 크기로 삼았다. 좋은 알고리즘이란 그 크기의 잘 정의된 함수로 실행 시간이 상한되는 것이며, 아무리 큰 사례에서도, 그리고 모든 크기에서 그 상한이 성립해야 한다고 요구했다. 작은 사례 몇 개를 일부러 어렵게 심어 기준을 왜곡하는 일을 막기 위해서였다. 그렇게 그는 자신의 블라섬(blossom) 알고리즘이 정점 수 n에 대해 n⁴ 수준의 난이도를 가진다고 밝혔다.
흥미롭게도 에드먼즈는 이 정의에 완전히 만족하지 못했다. 경직된 기준이 아직 그 기준에 들어맞는지 알 수 없거나 들어맞지 않는 것으로 알려진 알고리즘의 실용적 발전을 가로막을 수 있다고 우려했고, 선형계획법의 심플렉스 방법이 '얼마나 좋은가'가 미해결 문제로 남아 있다는 점, 전기 스위칭 이론의 많은 중요한 아이디어가 이 기준에서는 명백히 '좋지 않다'는 점을 함께 적었다.
다항식=좋음이라는 편의, 그리고 그 대가
이후 리처드 카프(Richard Karp) 같은 형식주의자들은 '다항 시간은 좋고, 지수 시간은 나쁘다'를 합리적 정의로 받아들였다. 여기서 복잡도 이론이 출발했고, 수많은 문제가 다항 시간에 풀리는지 증명하거나 그렇지 않은 문제를 특징짓는 작업이 이어졌다. 문제는 다항식이 '좋음'의 완벽한 대리물이 아니라는 데 있다. n¹⁰⁰⁰처럼 기술적으로는 다항식이어도 현실에서 결코 좋지 않은 경우가 있고, 우리가 마주칠 수 있는 어떤 n에서도 지수함수 2ⁿ보다 큰 다항식도 존재한다. 그럼에도 우리는 이 정의를 밀고 나갔고, 결과적으로 현실의 계산과 동떨어진 복잡도 결과들의 혼란스러운 집합이 쌓였다.
이런 점근적 사고는 '갤럭틱 알고리즘', 즉 실행 시간이 너무 커서 우주 안에서는 결코 구현될 수 없는 개념적 절차를 설계하는 나쁜 습관을 부추긴다. 이번 주 OpenAI가 발표한 충족 가능성(satisfiability, SAT) 문제의 '준지수 시간' 알고리즘도 이 맥락에서 읽어야 한다. SAT는 가장 잘 알려진 NP-완전 문제 중 하나이며, 다항 시간 알고리즘을 찾으면 클레이 밀레니엄 상을 받는다. 준지수 시간은 다항 시간이 아니라, 실행 시간이 2^f(n) 형태로 상한되되 f가 '열(sub-linear)'인 경우, 즉 n이 커질 때 f(n)/n이 0으로 가는 경우를 뜻한다. OpenAI의 결과는 어떤 명시되지 않은 상수 d, C에 의존하는 다소 지저분한 형태였지만, 트위터에서는 50년 만의 가장 큰 순간으로 치켜세워졌고 여러 이론 전산학자도 호응했다.
'ⅹ 미만이면 완전 탐색'이라는 함정
그런데 결정적인 단서가 있다. 변수의 수가 약 10^(10²⁵) 규모의 값보다 작으면, 이 알고리즘은 1965년 에드먼즈가 '나쁘다'고 선언한 바로 그 완전 탐색을 수행한다. 이 임계값은 전혀 가늠할 수 없는 크기다. 우주의 원자 수가 대략 10⁸⁰개인데, 그보다 상상할 수 없을 만큼 크다. 우리가 현실에서 다룰 수 있는 모든 문제에서 이 절차는 사실상 지수 시간 부분 루틴을 호출한다는 뜻이다. 결국 준지수 시간이라는 결과는 무한대 근처의 기묘하고 접근 불가능한 영역에서만 의미를 가진다. 이는 '효율적'이라는 정의가 50년 전에 생각했던 것보다 더 부실했음을 보여주는 사례이며, 효율이나 좋음에 대해 사실상 아무것도 말해 주지 않는다.
에드먼즈가 당시 심플렉스를 언급한 것은 묘하게 예언적이다. 심플렉스는 역사상 가장 중요한 알고리즘으로 꼽히지만, 엄밀히 말하면 최악의 경우 실행 시간은 지수적이다. 대부분은 빠르되 지수적 단계를 밟는 이상한 사례를 구성할 수 있다. 그럼에도 전 세계 최적화 응용에서 실제로 배치되어 쓰인다. 이론적 분류와 실무적 효용 사이의 간극을 그는 1965년에 이미 내다본 셈이다.
더 아이러니한 점은 산업 규모의 SAT 문제를 푸는 매우 효율적인 알고리즘이 이미 존재한다는 사실이다. 일반적인 컴퓨터로도 수백만 개의 변수와 수백만 개의 절(clause)을 가진 문제를 풀 수 있고, 인텔의 한 엔지니어는 변수 10억 개와 절 40억 개짜리 문제를 하루 만에 풀어냈다. 실무자 입장에서 이번 발표의 교훈은 분명하다. 점근적 상한의 수식 형태만 보고 '효율'을 판단해서는 안 되며, 상수와 임계값, 그리고 실제 입력 규모에서의 거동을 함께 봐야 한다. 때로는 질문에 답을 하고 나서야, 우리가 처음부터 원했던 것이 다른 질문이었음을 깨닫게 된다.