preLoad Image preLoad Image
검색 바로가기
주메뉴 바로가기
주요 기사 바로가기
다른 기사, 광고영역 바로가기
중앙일보 사이트맵 바로가기
닫기
닫기

[문병로의 알고리즘여행] 불가능하다는 사실이 유용할 때도 있다

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

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

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

천재들이 시도해도 못 푼 문제
‘풀이 불가능’ 잠정 결론 지으면
최적의 답 찾으려는 시도 대신
‘괜찮은 답’ 모색으로 궤도 수정

쿠르트 괴델은 1931년 어떠한 정상적인 논리 체계 내에서도 근본적으로 풀 수 없는 문제가 존재한다는 것을 증명했다. 20세기 수학의 기념비적 업적이 된 불완전성 정리다. 정신질환을 앓던 괴델은 자신이 오래 못 살 것으로 생각하고 프린스턴 고등연구소의 선배 교수인 세기의 천재 폰 노이만에게 자신의 유고 정리를 부탁했다. 그러기로 약속한 노이만은 먼저 죽고 괴델은 노이만보다 21년이나 더 살다가 죽는다.
 
괴델의 논제는 문제를 풀 수 있느냐 없느냐다. 즉 계산의 가능성에 관한 것이다. 알고리즘 분야에서도 가능성에 관한 논의를 포함하지만 대개 풀 수 있는 문제들을 얼마나 빠른 시간에 풀 수 있느냐에 관심이 더 많다. 풀 수 있지만 너무 오래 걸리면 실용적 의미가 없다. 수행 ‘시간’은 알고리즘 연구의 중심축 중의 하나다.
 
1971년 스티븐 쿡과 레너드 레빈은 GSAT이란 문제를 빨리 풀 수 있으면 어마어마하게 많은 알고리즘 문제를 빨리 풀 수 있다는 것을 증명했다. 이어서 리처드 캅은 21개의 문제를 제시하며 이들 중 어느 하나라도 빨리 풀 수 있으면 GSAT 문제가 빨리 풀린다는 사실을 증명했다. 이러면 논리적 체인에 의해 앞의 ‘어마어마하게 많은’ 문제가 빨리 풀린다. 이런 식으로 한 문제를 빨리 풀 수 있으면 다른 문제가 빨리 풀리는 연결 관계를 가진 문제 군이 급속히 커졌는데, 이로부터 ‘NP-완비’라는 거대한 연구 분야가 만들어졌다. 쿡은 자신의 연구 결과가 그저 흥미로운 것 정도로 생각했고 후에 거대한 연구 분야를 만들 것이라고 전혀 짐작하지 못했다고 한다.
 
알고리즘여행 7/3

알고리즘여행 7/3

NP-완비는 현실적인 시간 내에 잘 안 풀리는 문제들에 대한 이야기다. 고객 방문 스케줄링 문제나 반도체 디자인에서 게이트들을 배치하고 연결하는 문제 등이 가까운 예다. 실로 다양한 문제들이 NP-완비 문제 군에 속한다. 알려진 것만 적어도 수만 개는 될 것이고 이론적으로 무한히 만들 수 있다. 이 그룹의 문제들은 현재까지의 기술로는 빨리(현실적인 시간 내에) 푸는 방법이 알려져 있지 않다. 이들 중 단 하나만 현실적인 시간에 해결되면 순식간에 이 군의 모든 문제들이 현실적인 시간에 해결되어 버린다. 현실적인 시간을 의미하는 전문적 정의가 있지만 여기서는 생략한다. 장난감 사이즈를 넘어서는 문제에 대해 어떤 컴퓨터든 돌려서 죽기 전에 결과를 볼 수 있다면 현실적인 시간에 속한다는 정도로만 받아들이자. 알고리즘 과목에서 배우는 대부분의 주제가 어떻게 잘할 것인가에 관한 이야기인데 반해 NP-완비는 뭐가 잘 안되는가에 관한 이야기다.
 
클레이 수학연구소에서 21세기에 접어들면서 세기의 7대 난제를 정하고 각각에 대해 100만 달러씩 상금을 걸었다. 그중 하나가 “P=NP인가?”라는 질문이다. NP-완비 문제 중 하나만 현실적인 시간에 풀면 이 질문에 대한 답을 얻을 수 있어 상금을 받는다. 아마도 그런 일은 없을 것이고 현실적인 시간에 풀 수 없다는 것을 증명하는 것으로 결론이 날 것이다.  
 
7대 난제 중 하나인 푸앵카레 추측은 2002년 러시아 수학자 그리고리 페렐만이 증명했다. 페렐만은 100만 달러를 거부하고 허드렛일을 하는 어머니와 궁핍한 생활을 하고 있다.
 
어떤 문제가 잘 안 풀리면 자신의 지적 역량이 부족해서 그런지, 문제 자체가 어려워서 그런지 모르는 불안한 상태가 된다. 그 문제가 NP-완비에 속한다는 것이 판명되면 이런 걱정을 접어둘 수 있다. 지난 수십 년간 많은 천재들이 시도했지만 단 한 명도 해내지 못한 일이기 때문에 거의 불가능할 것이라고 잠정 결론지을 수 있다. 그러면 주어진 시간 내에 최적 품질은 보장할 수 없지만 꽤 괜찮은 답을 찾는 것을 목표로 하면 된다.
 
필자의 연구실에서 박사학위를 취득한 최성순 박사는 영어 대화도 잘 안 되는 상태로 실리콘 밸리의 반도체 자동 디자인 툴을 만드는 회사에 취업했다. 처음엔 좀 고생하더니 몇 년 후 게이트의 배치와 연결 품질에 관한 NP-완비 문제의 답을 획기적으로 개선하여 회사를 도약시켰다. 이 그룹의 문제들은 이미 어떤 좋은 알고리즘이 알려졌어도 최적을 보장하지는 못하므로 항상 개선될 여지가 남아 있는 장점이 있다.
 
문병로 서울대 컴퓨터공학부 교수
AD
온라인 구독신청 지면 구독신청

PHOTO & VIDEO

shpping&life

많이 본 기사

댓글 많은 기사