출처: 중앙일보 2020년 6월 5일자 [문병로의 알고리즘 여행]

알고리즘은 인간의 사고와 분리해서 생각할 수 없다. 전통적인 알고리즘은 대개 시간만 충분하면 인간이 할 수 있는 일은 대신한다. 해답을 찾는 과정도 인간의 머릿속에서 먼저 구상하고 이 과정을 알고리즘으로 구현한다. ‘인간다운’ 알고리즘이라 할 수 있다. 학부의 알고리즘 클래스에서 배우는 대부분의 알고리즘이 이 부류에 속한다. 80년대 AI 분야를 풍미하던 전문가 시스템도 이 부류에 속한다.

반면 인간이 찾기 힘들거나 근본적으로 찾을 수 없는 해답을 찾는 알고리즘들이 있다. 이 부류에는 인간의 타고난 불합리성을 이용해서 인간이 비켜가는 좋은 해답을 찾는 스타일이 있고, 너무 복잡해서 인간이 근본적으로 찾을 수 없는 해답을 찾아가는 스타일도 있다. 이런 알고리즘으로 문제의 해답을 찾다보면 우리 인간이 얼마나 근본적인 한계를 지닌 존재인지를 실감하게 된다. 방대한 문제의 공간을 생각하면 인간의 머리가 조금 더 좋고 좋지 않고는 별 심각한 차이가 아니다.

두 개의 행렬을 곱하는 작업은 행렬 크기의 3제곱에 비례하는 시간이 든다는 사실은 누구도 의심하지 않은 사실이었다. 1969년에 스트라센이라는 독일 청년이 행렬 크기의 2.81제곱에 비례하는 시간이 드는 알고리즘을 내놓았을 때 수학과 컴퓨터 세계는 경악했다. 그것을 찾기까지의 경우의 수가 도저히 인간으로서 가능할 것 같지 않았다. 스트라센은 천재적인 머리로 가능성 있는 공간으로 좁히고 좁혀서 하나의 알고리즘을 찾아냈다. 이후에 위노그라드가 같은 시간이 드는 다른 알고리즘을 찾아냈다.  

필자는 박사과정때부터 이들의 알고리즘과 동일한 시간이 드는 다른 알고리즘이 없을까 궁금했다. 스트라센과 같은 방식으로 필자가 직접 문제공간을 뒤져서는 승산이 없다. 저런 천재와 같은 방식으로 경쟁해야 한다면 그냥 찻집이나 하나 차려 책 읽으면서 사는 게 나을 것이다. 대신에 필자의 전문 분야인 탐색 알고리즘을 개발해서 공간을 뒤지도록 하면 어쩌면 가능하지 않을까 하는 생각을 했다.

서울대에 부임한 이후 간헐적으로 이 문제에 도전했는데 실패를 거듭했다. 모든 경우의 수를 따지는 것은 영겁의 시간이 들어 불가능했다. 선형대수적 지식을 최대한 이용해서 시간을 단축하면 모든 경우의 수를 따지는 데 6700만년 정도까지는 줄일 수 있었다. 여전히 불가능한 시간이다. 극심한 축소 탐색을 할 수밖에 없다. 유전 알고리즘과 다른 알고리즘들을 혼합해서 시도했는데 적어도 5년 이상 실패를 거듭했다. 2005년 학부생으로 필자의 대학원 유전 알고리즘을 수강하던 오승현 학생과의 연구에서 드디어 스트라센과 동일한 복잡도를 가진 알고리즘을 608개 찾아내었다. 이 중에는 스트라센과 위노그라드의 알고리즘도 포함되어 있었다. 그들의 알고리즘 말고도 같은 품질의 알고리즘이 적어도 606개나 더 있다는 사실을 발견했다. 필자의 연구 이력에서 가장 자랑스러운 논문 중 하나인데 재미있게도 학부생이랑 만들어낸 결과다. 우리가 개발한 알고리즘이 하나를 찾아내는데 평균 20분이 걸리지 않았다. 개인의 역량은 스트라센에 못 미치지만 “신에게는 공간을 여행하는 막강한 교통수단이 있습니다” 이런 기분이었다. 이런 알고리즘은 인간답지 않다.

인간을 보는 두 가지 대조적인 관점이 있다. 하나는 인간이 우주에서 특별한 사명을 가진 존재라는 관점이다. 이 관점의 인간은 신의 외양을 재현하고 철저히 합리성을 추구하는 존재다. 다른 관점은 인간은 불완전한 존재고 진화의 과정에서 우연히 운 좋게 지구를 지배하게 된 고등 영장류라는 관점이다. 이 관점의 인간은 불완전하고, 비합리적이고, 동물적이다. 전통적인 알고리즘은 전자의 관점과 통한다. 반면 최근 이슈가 되는 알고리즘들은 후자의 관점과 통한다. 과정이 정확히 드러나지 않는 좋은 결과를 받아들여야 하는 시대가 되었다. ‘인간답지 않은’ 알고리즘의 시대가 왔다.  

서울대학교 컴퓨터공학부 문병로 교수