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

대부분의 연구는 무얼 어떻게 잘해볼 것인가에 관한 것이다. 이런 가운데 몇몇 천재들은 자신들 분야의 근본적인 한계를 규명한다.

쿠르트 괴델은 1931년 어떠한 정상적인 논리 체계 내에서도 근본적으로 풀 수 없는 문제가 존재한다는 것을 증명했다. 20세기 수학의 기념비적 업적이 된 불완전성 정리다. 정신질환을 앓던 괴델은 자신이 오래 못 살 것으로 생각하고 프린스턴 고등연구소의 선배 교수인 세기의 천재 폰 노이만에게 자신의 유고 정리를 부탁했다. 그러기로 약속한 노이만은 먼저 죽고 괴델은 노이만보다 21년이나 더 살다가 죽는다.

괴델의 논제는 문제를 풀 수 있느냐 없느냐다. 즉 계산의 가능성에 관한 것이다. 알고리즘 분야에서도 가능성에 관한 논의를 포함하지만 대개 풀 수 있는 문제들을 얼마나 빠른 시간에 풀 수 있느냐에 관심이 더 많다. 풀 수 있지만 너무 오래 걸리면 실용적 의미가 없다. 수행 ‘시간’은 알고리즘 연구의 중심축 중의 하나다.

1971년 스티븐 쿡과 레너드 레빈은 GSAT이란 문제를 빨리 풀 수 있으면 어마어마하게 많은 알고리즘 문제를 빨리 풀 수 있다는 것을 증명했다. 이어서 리처드 캅은 21개의 문제를 제시하며 이들 중 어느 하나라도 빨리 풀 수 있으면 GSAT 문제가 빨리 풀린다는 사실을 증명했다. 이러면 논리적 체인에 의해 앞의 ‘어마어마하게 많은’ 문제가 빨리 풀린다. 이런 식으로 한 문제를 빨리 풀 수 있으면 다른 문제가 빨리 풀리는 연결 관계를 가진 문제 군이 급속히 커졌는데, 이로부터 ‘NP-완비’라는 거대한 연구 분야가 만들어졌다. 쿡은 자신의 연구 결과가 그저 흥미로운 것 정도로 생각했고 후에 거대한 연구 분야를 만들 것이라고 전혀 짐작하지 못했다고 한다.

NP-완비는 현실적인 시간 내에 잘 안 풀리는 문제들에 대한 이야기다. 고객 방문 스케줄링 문제나 반도체 디자인에서 게이트들을 배치하고 연결하는 문제 등이 가까운 예다. 실로 다양한 문제들이 NP-완비 문제 군에 속한다. 알려진 것만 적어도 수만 개는 될 것이고 이론적으로 무한히 만들 수 있다. 이 그룹의 문제들은 현재까지의 기술로는 빨리(현실적인 시간 내에) 푸는 방법이 알려져 있지 않다. 이들 중 단 하나만 현실적인 시간에 해결되면 순식간에 이 군의 모든 문제들이 현실적인 시간에 해결되어 버린다. 현실적인 시간을 의미하는 전문적 정의가 있지만 여기서는 생략한다. 장난감 사이즈를 넘어서는 문제에 대해 어떤 컴퓨터든 돌려서 죽기 전에 결과를 볼 수 있다면 현실적인 시간에 속한다는 정도로만 받아들이자. 알고리즘 과목에서 배우는 대부분의 주제가 어떻게 잘할 것인가에 관한 이야기인데 반해 NP-완비는 뭐가 잘 안되는가에 관한 이야기다.

클레이 수학연구소에서 21세기에 접어들면서 세기의 7대 난제를 정하고 각각에 대해 100만 달러씩 상금을 걸었다. 그중 하나가 “P=NP인가?”라는 질문이다. NP-완비 문제 중 하나만 현실적인 시간에 풀면 이 질문에 대한 답을 얻을 수 있어 상금을 받는다. 아마도 그런 일은 없을 것이고 현실적인 시간에 풀 수 없다는 것을 증명하는 것으로 결론이 날 것이다.

7대 난제 중 하나인 푸앵카레 추측은 2002년 러시아 수학자 그리고리 페렐만이 증명했다. 페렐만은 100만 달러를 거부하고 허드렛일을 하는 어머니와 궁핍한 생활을 하고 있다.

어떤 문제가 잘 안 풀리면 자신의 지적 역량이 부족해서 그런지, 문제 자체가 어려워서 그런지 모르는 불안한 상태가 된다. 그 문제가 NP-완비에 속한다는 것이 판명되면 이런 걱정을 접어둘 수 있다. 지난 수십 년간 많은 천재들이 시도했지만 단 한 명도 해내지 못한 일이기 때문에 거의 불가능할 것이라고 잠정 결론지을 수 있다. 그러면 주어진 시간 내에 최적 품질은 보장할 수 없지만 꽤 괜찮은 답을 찾는 것을 목표로 하면 된다.

필자의 연구실에서 박사학위를 취득한 최성순 박사는 영어 대화도 잘 안 되는 상태로 실리콘 밸리의 반도체 자동 디자인 툴을 만드는 회사에 취업했다. 처음엔 좀 고생하더니 몇 년 후 게이트의 배치와 연결 품질에 관한 NP-완비 문제의 답을 획기적으로 개선하여 회사를 도약시켰다. 이 그룹의 문제들은 이미 어떤 좋은 알고리즘이 알려졌어도 최적을 보장하지는 못하므로 항상 개선될 여지가 남아 있는 장점이 있다.

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