한 컴퓨터 과학자의 ‘충격적인’ 증명은 컴퓨터 과학에서 가장 유명한 질문 중 하나에 대해 50년 만에 첫 진전을 이룩했다.
한 컴퓨터 과학자의 ‘충격적인’ 증명은 컴퓨터 과학에서 가장 유명한 질문 중 하나에 대해 50년 만에 첫 진전을 이룩했다.
Irene Pérez for Quanta Magazine
2024년 7월의 어느 오후, 라이언 윌리엄스는 스스로의 생각이 틀렸음을 증명하고자 했다. 컴퓨팅에서 시간과 메모리의 관계에 대한 놀라운 발견을 한 지 두 달이 지난 시점이었다. 그가 그린 러프한 증명의 요점은, 메모리가 컴퓨터 과학자들이 생각했던 것보다 더 강력하다는 것이었다. 즉, 아주 적은 양의 메모리로도 모든 가능한 계산에서 아주 많은 시간만큼의 도움을 받을 수 있다는 것이다. 워낙 비현실적으로 들렸기에 오류가 있을 거라 생각하고 증명을 미뤄두고 다른 덜 미친 듯한 아이디어에 집중했다. 이제야 시간을 내어 오류를 찾으려 다시 들여다 보게 된 것이다.
하지만 그러지 않았다. 몇 시간에 걸쳐 논증을 곱씹은 결과, 윌리엄스는 단 한 가지의 결점도 찾지 못했다.
“정말 미쳐가는 줄 알았어요.” MIT의 이론 컴퓨터 과학자인 윌리엄스는 말했다. 처음으로, 그는 자신의 작업에서 메모리가 정말 그렇게까지 강력할 수도 있다는 가능성을 받아들이기 시작했다.
다음 몇 달 간 그는 세부사항을 보완하고, 모든 단계를 점검하며, 소수의 연구자들에게 피드백을 구했다. 그리고 2월, 그는 마침내 자신의 증명을 온라인에 공개했다. 그리고 큰 호평을 받았다.
“놀랍고, 아름답다.” 프린스턴에 있는 고등연구소의 이론 컴퓨터 과학자 아비 위그더슨은 말했다. 소식을 들은 즉시 위그더슨은 윌리엄스에게 축하 이메일을 보냈다. 제목은 “You blew my mind.”
시간과 메모리(공간이라고도 한다)는 계산에서 가장 근본적인 두 자원이다. 모든 알고리즘은 실행하는 데 시간이 걸리고, 실행 중 데이터를 저장할 공간도 필요하다. 지금까지 특정 작업을 수행하는 알고리즘은 실행시간에 비례하는 공간을 필요로 했고, 연구자들은 이보다 더 효율적인 방식은 없으리라 오랫동안 생각해왔다. 그러나 윌리엄스의 증명은 어떤 알고리즘이든 — 그것이 무슨 일을 하든 — 훨씬 더 적은 공간만 사용하는 형태로 변환하는 수학적 절차가 있음을 입증했다.
라이언 윌리엄스는 계산에서 시간과 공간의 관계에 대한 이정표 증명으로 동료들을 놀라게 했다.
Katherine Taylor for Quanta Magazine
더구나, 이렇게 공간이라는 제한된 자원으로 무엇을 계산할 수 있는지에 대한 이 결과는, 동시에 시간이라는 한정된 자원으로 무엇을 할 수 없는지에 대한 결과도 함의하고 있다. 두 번째 결과 자체는 놀랍지 않다. 연구자들은 그것이 사실이리라 예상했지만, 증명 방법을 전혀 몰랐다. 윌리엄스의 해법은 첫 결과의 힘을 압도적으로 이용하는 것으로, 마치 살인혐의자를 유죄로 증명하려고 전 세계 모든 사람의 알리바이를 완벽히 증명하는 것처럼 과하게 보일 정도다. 이 결과는 컴퓨터 과학에서 가장 오래된 미해결 문제 중 하나에 도전할 새로운 방법을 제시할 수도 있다.
“놀랄 만한 결과이며 엄청난 진전이에요.” 워싱턴 대학의 컴퓨터 과학자 폴 빔은 말했다. “또한 이 정도로 놀라운 결과는 라이언이기에 가능했다는 것도 덜 놀랍죠.”
46세의 윌리엄스는 열린 표정에 머리에 회색 빛이 살짝 드러난다. MIT 스타타 센터의 다채로운 첨탑을 내려다보는 그의 사무실은 공간의 창의적 활용을 상징한다. 요가 매트 두 장은 창턱을 즉석 독서공간으로 만들었고, 책상은 기묘한 구석에 놓여 있어 넓게 수학 낙서로 빼곡한 대형 화이트보드를 마주보는 소파 공간을 확보한다.
MIT는 윌리엄스가 자란 앨라배마의 시골에서 아주 먼 곳이다. 그는 50에이커 규모의 농장에서 자랐으며, 일곱 살 때 엄마가 군 전체를 가로질러 참가시킨 영재 학술 수업에서 처음 컴퓨터를 봤다. 디지털 불꽃놀이를 보여주는 단순한 프로그램에 매료됐던 기억이 있다.
“중앙에서 랜덤 색을 선택해 랜덤 방향으로 쏘는 프로그램이었어요. 매번 어떤 그림이 나올지 예측할 수 없었죠.” 컴퓨터의 세계는 무한한 가능성을 가진 멋진 놀이터로 보였다. 어린 윌리엄스는 푹 빠졌다.
“저는 미래의 컴퓨터에서 실행될 프로그램을 종이에 혼자서 짜곤 했어요. 부모님은 저를 어찌할지 몰랐죠.”
윌리엄스의 사무실 역시 그의 새 연구 결과처럼 공간의 창의적 활용을 보여준다.
Katherine Taylor for Quanta Magazine
나이가 들면서 그는 상상의 컴퓨터에서 실제 컴퓨터로 옮아갔다. 고교 마지막 2년은 앨라배마 과학수학고로 전학했다. 이곳은 명성이 높은 기숙사형 공립학교로, 여기서 그는 컴퓨터 과학의 이론적 측면을 처음 접했다.
“컴퓨터에 대해 수학적으로 생각하는 방법이 있다는 것을 알게 됐고, 그게 제가 하고 싶은 거였어요.”
윌리엄스는 이론 컴퓨터 과학의 한 갈래인 계산복잡도 이론에 특히 매료됐다. 이는 정렬이나 소인수분해 같은 계산 문제를 해결하기 위해 필요한 자원(예를 들면 시간, 공간 등)에 관한 학문이다. 대부분의 문제는 각각 시간과 공간 요구조건이 다른 여러 알고리즘으로 풀 수 있다. 복잡도 이론가는 가장 효율적인 알고리즘(가장 빠르거나 가장 적은 공간을 쓰는)이 필요한 자원에 따라 문제를 복잡도 계급(complexity class)라는 범주로 나눈다.
하지만 계산 자원을 수학적으로 엄밀히 연구하려면 어떻게 해야 할까? 분 단위 시간과 메가바이트 공간을 단순 비교하듯 접근해선 별 성과를 못낸다. 진전을 이루려면 올바른 정의에서 시작해야 한다.
이 정의들은 제한된 자원으로 살아남은 개척자 컴퓨터 과학자 유리스 하트마니스(Juris Hartmanis)의 연구에서 비롯되었다. 그는 1928년 라트비아의 유력한 집안에서 태어났으나, 2차대전 발발로 어린 시절이 크게 흔들렸다. 소련 점령군은 아버지를 체포해 처형했고, 하트마니스는 전쟁 후 난민 수용소에서 고등학교를 마쳤다. 대학에 진학한 뒤 교재를 살 수 없어 강의 노트를 아주 자세히 필기하는 것으로 보완했다.
“어려움을 극복해야 하는 데에도 장점이 있죠.”라고 그는 2009년 인터뷰에서 회고했다. 하트마니스는 1949년에 미국으로 이민했고, 각종 아르바이트 — 농기계 만들기, 철강 제조, 집사 일 등 — 을 하며 캔자스 시티 대학에서 수학을 공부했다. 젊은 이론 컴퓨터 과학 분야에서 화려한 경력을 쌓았다.
1960년, 뉴욕 셴터디의 GE 연구소에서 일하던 하트마니스는 여름 인턴으로 온 대학원생 리처드 스턴스를 만났다. 둘은 획기적인 논문 두 편에서 시간과 공간의 수학적 정의를 세웠다. 이 개념 정의로 연구자들은 두 자원을 비교하고 복잡도 계급을 분류할 수 있는 언어를 갖게 됐다.
1960년대에 유리스 하트마니스는 컴퓨터 과학자들이 공간과 시간을 분석하는 데 사용하는 정의들을 확립했다.
Division of Rare and Manuscript Collections, Cornell University Library
가장 중요한 계급 중 하나는 "P"라는 소박한 이름을 갖는다. 대략적으로, "합리적 시간 내에 풀 수 있는" 모든 문제를 비롯한다. 이에 상응하는 공간 복잡도 계급은 "PSPACE"라 불린다.
이 두 집합의 관계는 복잡도 이론의 핵심 질문 중 하나다. 모든 P의 문제는 PSPACE에도 포함된다. 빠른 알고리즘은 컴퓨터 메모리 공간을 많이 사용할 시간이 없기 때문이다. 만약 이 반대도 참이라면, 두 계급은 동치이며, 공간과 시간의 계산적 힘은 비슷해진다. 하지만, 복잡도 이론가들은 PSPACE가 훨씬 큰 집합이며, P에 없는 문제가 많다고 본다. 다시 말해, 공간이 시간보다 훨씬 더 강력한 계산 자원이라는 것이다. 이는 알고리즘이 같은 작은 메모리 공간을 반복해서 쓸 수 있지만, 시간은 돌려받을 수 없어서 재사용이 불가능하기 때문이라는 직관에서 나온다.
“직관적으로 너무 쉽죠. 공간은 재사용이 되지만 시간은 재사용이 안 돼요.” 윌리엄스는 말했다.
그러나 복잡도 이론가는 직관에 만족하지 않는다. 엄밀한 증명을 원한다. PSPACE가 P보다 크다는 걸 보일려면, 어떤 PSPACE 문제는 빠른 알고리즘이 원천적으로 불가능함을 보여야 한다. 어디서 시작해야 할까?
이 여행은 1965년, 하트마니스가 코넬 대학의 신설 컴퓨터 과학 학과장으로 부임하면서 시작된다. 그는 복잡도 이론 연구 허브로 학과를 키웠고, 1970년대 초 연구자 존 홉크로프트와 볼프강 파울이 시간과 공간의 정밀한 연결고리를 찾기로 했다.
이들은 P 대 PSPACE 문제를 풀기 위해, 제한된 시간 안에 어떤 계산을 아예 할 수 없다는 것을 증명해야 함을 알았다. 하지만 부정을 증명하는 것은 어려운 일이다. 대신, 문제를 뒤집어 제한된 공간으로 무엇을 할 수 있나 탐험하기로 한다. 그들은 일정 공간만 허용된 알고리즘이, 시간만 좀 더 많은 알고리즘과 같은 문제를 모두 풀 수 있음을 보일 수 있을까를 노렸다. 그게 된다면, 공간이 시간보다 약간 더 강력하단 증거가 된다. PSPACE가 P보다 크다는 증명에 작은 초석이라도 될 수 있다.
이들은 변환(simulation)이라 부르는 아이디어에 착안한다. 기존 알고리즘을 주어진 공간-시간 예산이 달라지도록 변환해서 같은 문제를 푸는 새 알고리즘을 만든다. 예를 들어, 서가의 책을 빠르게 정렬하는 알고리즘이 있지만, 수십 개 더미로 책을 펼쳐야만 한다고 치자. 아파트 공간을 적게 쓰려면 시간이 오래 걸리는 다른 방법이 더 나을 수 있다. 시뮬레이션은 원래 알고리즘에서 공간을 아끼는 새로운 알고리즘을 수학적으로 만들어 주는 절차다.
알고리즘 디자이너들은 오래전부터 정렬 등 특정 작업에 대해 공간-시간 상충관계를 연구해왔다. 하지만 홉크로프트와 파울은 모든 문제, 모든 알고리즘에 해당하는 범용적인 절차 — 즉, 작업 종류에 상관없이 무조건 공간을 덜 쓰게 만드는 방법 — 를 원했다. 이는 특정 문제마다 최적화하는 기존 방식보다 당연히 효율이 떨어질 수밖에 없다. 그래도 당시엔 어떤 범용 절약법도 알려져 있지 않아, 공간을 조금이라도 아끼는 게 큰 진전이었다.
이 돌파구는 1975년, 이들이 젊은 연구자 레슬리 밸리언트와 힘을 합치면서 나왔다. 이 셋은 어떤 알고리즘이든, 원래 주어진 시간보다 살짝 적은 공간에 맞춰 동등한 알고리즘을 만드는 시뮬레이션 절차를 고안했다.
“얼마만큼의 시간 안에 할 수 있다면, 아주 약간이라도 적은 공간으로도 할 수 있다.” 밸리언트가 말했다. 이는 공간과 시간의 연결고리 찾기 여정의 첫 거대한 발걸음이었다.
1975년, 레슬리 밸리언트는 공간이 시간보다 약간 더 강력한 계산 자원이라는 걸 증명하는 데 기여했다.
Katherine Taylor for Quanta Magazine
하지만 곧 진전이 멈췄다. 범용성을 가진 시뮬레이션 때문에, 어떤 문제들은 직관적으로 생각해도 거의 시간만큼 공간이 필요해 보였다. 더 효율적인 범용 시뮬레이션은 불가능할 것이다. 파울과 두 연구자는 1979년 정말로 불가능함을 입증했다. 단 한 가지 상식적인 조건만 두면 — 즉, 한 데이터 조각이 한 번에 한 공간만 차지해야 한다는 조건이다.
“누구나 더 나은 것은 불가능하다 여겼죠.” 위그더슨이 말했다.
파울의 결과는, P 대 PSPACE 문제를 풀려면 아예 시뮬레이션이라는 접근 자체를 버리고 완전히 다른 방법을 써야 함을 시사했다. 하지만 누구도 뾰족한 해법을 내놓지 못했다. 문제는 50년간 그 자리에 멈춰 있었다. 윌리엄스가 마침내 이 교착 상태를 깰 때까지는.
먼저, 그는 대학을 마처야 했다.
1996년, 윌리엄스는 대학 지원을 했다. 복잡도 이론을 전공하려면 집을 멀리 떠나야 한다는 걸 알고 있었지만, 부모님이 미국 서해안과 캐나다 진학은 금지시켰다. 남은 선택지 중, 코넬 대학은 그가 애정하는 분야의 역사적 뿌리이기에 특별해 보였다.
“하트마니스라는 인물이 시간, 공간 복잡도 계급을 정의했죠. 내겐 그게 컸어요.”
윌리엄스는 장학금과 함께 코넬에 입학했다. 복잡도 이론가가 되기 위해선 뭐든지 하겠다는 일념이었다. 동기들에게도 그의 몰두는 크게 각인됐다.
“완전히 복잡도 이론에 미쳐 있었죠.” 텍사스 오스틴대 컴퓨터 과학자 스콧 애런슨은 한 학번 아래에서 윌리엄스를 봤던 시절을 회상했다.
윌리엄스는 학부 시절 공간과 시간의 관계에 흥미를 가졌지만, 기회가 오기 전까지 연구에 착수하지 못했다.
Katherine Taylor for Quanta Magazine
하지만 그는 2학년 때 복잡도 이론 수업의 수학적 엄밀성에 뒤쳐지기 시작했다. 이론 컴퓨터 과정에서 평범한 성적을 받고, 교수는 좀 더 다른 진로를 생각해보라 권했다. 윌리엄스는 포기를 모른 채, 더 높은 학년 대상 이론 과정에 도전해 괄목할 만한 성적을 올려 대학원 지원시 어필하고자 했다. 그 과목 담당이 바로 하트마니스였다.
윌리엄스는 몇주 째 하트마니스의 오피스 아워를 방문했고, 거의 매번 혼자였다. 끈기의 보상으로 A를 받았고, 다음 학기엔 하트마니스 지도 하에 개인 연구 프로젝트를 하게 됐다. 둘의 주간 미팅은 대학 졸업 때까지 계속됐다. 하트마니스는 독창성을 기르라 격려했고, 부드럽게 막다른 길은 피하게 도왔다.
“그분에게 무척 많은 영향을 받았어요. 지금도 그렇고요.”
NSF 대학원 연구 장학금을 따냈음에도, 윌리엄스는 박사 지원에서 모두 탈락했다. 하트마니스는 동료에게 전화하더니, 코넬 1년 석사 과정에 합격했다고 윌리엄스에게 알려줬다. 1년 뒤 다시 박사에 도전, 이번엔 경험을 살려 합격했다.
윌리엄스는 이후 줄곧 복잡도 이론 연구를 이어왔다. 2010년, 박사학위 후 4년 만에 컴퓨터 과학 최대 난제(복잡한 문제의 본질)에 대한 중요한 진전을 보여 명성을 굳혔다.
그런데도 P 대 PSPACE 문제는 연구하지 않았다. 학부생때부터 그의 관심사였지만, 딱히 연구 아이디어를 얻지 못했다.
“항상 뒷머리에 머물렀죠. 하지만 꼭 하고 싶던 얘기를 찾지 못했어요.”
그러다 지난해, 마침내 기회가 왔다.
이번 결과의 배경에는, 극도로 제한된 메모리로 할 수 있는 계산은 무언가에 대한 다른 질문이 있엇다. 2010년, 스티븐 쿡과 동료들은 트리 평가 문제를 고안, 특정 공간 이하로는 어떤 알고리즘도 못 푼다는 걸 증명했다. 하지만 허점이 있었다. 그 증명은 파울이 예전에 썼던 바로 그 상식 — 즉, 이미 찬 공간에 데이터를 더 못쓴다는 가정에 의존했다.
10년 넘게 이 허점을 메우려 했으나, 2023년 제임스 쿡과 이안 머츠가 혁신적인 알고리즘으로 이 문제를 훨씬 적은 공간에 풀어버린 것이다. 이전 증명은 데이터 비트가 마치 조약돌처럼, 반드시 서로 다른 자리만 차지해야 한다고 가정했다. 하지만, 꼭 그런 식이 아닐 수도 있다. “사실 조약돌을 약간 겹쳐서 압축시켜 생각할 수도 있음을 이번에 본 셈이죠.” 빔이 말했다.
제임스 쿡(왼쪽)과 이안 머츠는 특정 문제를 상상 이상으로 적은 공간에 풀 수 있는 새 알고리즘을 개발했다.
Colin Morris; Michal Koucký
이 알고리즘은 많은 연구자들의 관심을 불러일으켰지만, 트리 평가 문제 외에 크게 의미가 있는지 불명확했다. “이 방법이 시간 대 공간 논쟁의 본질에 영향을 줄 거라는 생각은 아무도 못 했죠.” 위그더슨이 말했다.
라이언 윌리엄스는 예외였다. 2024년 봄, 학생들이 자신이 맡은 수업의 기말 프로젝트로 쿡·머츠 논문 발표를 했다. 학생들의 열정에 자극받아 논문을 자세히 읽었다. 곧 아이디어가 떠올랐다. 쿡·머츠 방식은 공간 사용량을 줄여주는 범용 도구임을 깨달은 것이다. 이를 활용해 시뮬레이션을 새로 구성하면, 기존 홉크로프트-파울-밸리언트의 범용 시뮬레이션보다는 훨씬 나은 결과가 나오지 않을까?
기존 결과는 주어진 시간 제한을 가진 알고리즘을 공간 면에서 약간만 줄여주는 새로운 알고리즘으로 바꿔주는 거였다. 윌리엄스는, 조약돌 겹치기 시뮬레이션이라면 새로운 알고리즘이 원본 시간의 제곱근 정도만 공간을 차지하게 만들 수 있다는 걸 봤다. 이 방법의 동등한 알고리즘은 매우 느려 실용적 의미는 없다. 하지만 이론적으로는 혁명적이다.
50년 동안 그들 시뮬레이션보다 더 나은 범용 변환이 불가능하다고 여겨졌다. 윌리엄스의 아이디어가 맞는다면, 기록을 깨는 수준이 아니라 완전히 박살 내는 것이었다.
“생각해 봤더니 그게 정말일리 없었다는 결론에 계속 이르렀죠.” 그래서 한동안 미루다, 7월 절호의 순간에 논거의 오류를 찾으려다 결국 실패한다. 결함이 없다는 걸 깨닫자, 그는 몇 달간 증명을 명확하게 다듬는 데 집중했다.
2월 말, 그는 마침내 최종 논문을 공개했다. 쿡과 머츠도 모두 놀랐다. “그 소식 듣고 한참 산책을 해야 했어요.” 머츠가 말했다.
밸리언트는 윌리엄스가 옛 결과를 뛰어넘은 것을 등굣길에 미리 들었다. 그는 하버드대에서 수년간 가르쳤고, 윌리엄스의 MIT 사무실과 매우 가까웠다. 눈 내린 2월, 버스에서 우연히 마주쳤고, 윌리엄스는 증명 내용을 설명했다.
“무척 감명 깊었어요. 50년만에 최고라면 뭔가 제대로 한 거죠.”
윌리엄스의 새 시뮬레이션은 공간의 계산 능력에 대해 긍정적 결과를 증명했다. 즉, 적은 공간을 쓰는 알고리즘이 더 많은 시간이 필요한 문제도 풀 수 있음을 보였다. 그리고 몇 줄의 수식만으로, 시간의 계산 능력은 이런 수준을 못 넘어서, 몇몇 문제는 공간보다 더 많은 시간 없인 풀지 못함도 증명했다. 이 두 번째(부정적) 결과는 연구자들이 예견하던 것이다. 이상한 점은, 윌리엄스가 모든 알고리즘에 적용되는, 거대한 결과를 먼저 증명하고 거기서 고작 줄 단위의 수식으로 이런 부정성을 끌어냈다는 것이다.
“아직도 믿기 힘들어요. 너무 꿈만 같아서.”
윌리엄스는 쿡·머츠 기법을 활용해 공간과 시간 사이를 더욱 강하게 이어주는 50년 만의 첫 성과를 냈다.
Katherine Taylor for Quanta Magazine
윌리엄스의 두 번째 결과는 정성적으로 들으면 P 대 PSPACE 문제의 해법처럼 느껴질 수 있다. 실제로는 규모의 차이다. P, PSPACE는 아주 넓은 복잡도 계급이다. 윌리엄스의 결과는 훨씬 미세한 레벨에서 작동한다. 그는 공간과 시간의 힘에 수치적인 간격이 있음을 보였다. PSPACE가 P보다 큼을 보여려면, 이 간격이 훨씬 커져야 한다.
그것은 인도블록 틈새를 크로우바로 비집어 그랜드캐니언만하게 만드는 과업에 비유할 수 있다. 하지만 윌리엄스 시뮬레이션을 반복해서 매번 조금씩 공간을 줄일 수 있다면 가능할지도 모른다. 크로우바 길이를 반복적으로 늘리는 식이다. 지금 알고리즘 구조로는 이 반복 개선이 안된다. 이것이 근본적 한계인지는 아무도 모른다.
“최후의 병목일 수도, 50년짜리 병목일 수도 있죠. 아니면 누가 다음주에 풀 수도 있어요.” 밸리언트가 말했다.
만약 정말 다음 주에 풀린다면, 윌리엄스는 땅을 칠 것이다. 그는 논문 쓰기 전 몇 달간 쥐어짜 보려 애썼지만, 연장은 실패했다. 그럼에도, 공간 탐험이 언젠가 다른 문제에 획기적 돌파구로 이어지리란 믿음은 크다.
“항상 내가 진짜 증명하고 싶던 걸 딱 맞춰 증명하긴 어렵죠. 하지만 내가 실제로 증명하는 게 때론 내가 원한 것보다 훨씬 나아요.”
편집자 주: 스콧 애런슨은 Quanta Magazine의 자문위원단입니다.
