P vs NP 문제: “알고 보면 쉬운 문제가 답을 알기 전에도 쉬운 문제인지 증명하라.”


오늘은 인류 최대의 난제 (쿨럭…--;;) P vs NP 문제에 대해서 알아볼까 합니다.
역시 전공자가 아니라 제 글에 오류가 있을 가능성이 농후하고 오류에 대해서는 지적해 주시면 감사하겠습니다.

상암 월드컵 경기장에 한 가득 건초더미를 쌓아 놓았다고 칩시다. 거기 어딘가에 바늘이 하나 떨어져 있습니다. 그 건초더미들 속에서 숨겨진 바늘을 찾아야 합니다. 바늘을 찾는 사람이 건초를 한 줌씩 쥐고 와서 여러분에게 검사를 맞는다고 가정하면 여러분들이 그 한줌의 건초더미 속에 바늘이 있는 지 없는 지 확인하는 것은 아주 쉽습니다. 확인하는 데 그리 오랜 시간이 걸리지도 않을 것입니다. 하지만 상암 경기장을 가득 채운 건초 더미에서 실제 바늘을 찾은 일은 아주 어려운 작업입니다. 언제 문제가 해결될 지 도저히 가늠할 수가 없지요.

또 다른 예를 들어보겠습니다.
여러분들은 대학교 기숙사 사감입니다. 신학기가 되어서 기숙사에 들어올 학생들을 선발해야 합니다. 기숙사에 들어올 수 있는 인원은 100명인데 신청자는 모두 130명입니다. 그런데 사감인 여러분에게는 기숙사에 들어오면 말썽을 부릴 것 같은 학생들 리스트가 있어서 이 녀석들은 절대로 기숙사 입사가 허용되어서는 안 된다고 칩시다. 여러분 밑에 직원이 130명들 가운데 100명을 추린 리스트를 여러분에게 가져 온다고 합시다. 그런데 불행하게도 그 직원은 기숙사 신청자들 가운데 누가 요주의 인물들인지 모른다고 합시다.

직원이 어떤 명단을 만들어서 가져왔을 때 그 명단이 허용이 될 지 안될지 확인하는 것은 아주 쉽습니다. 직원이 가져온 명단과 여러분이 가지고 있는 요주인 인물 명단을 서로 비교해서 요주의 인물이 한 명이라도 직원이 가지고 온 명단에 들어 있으면 그 명단을 휴지통으로 보내 버리면 되니까요. 그러니까 직원이 가지고 온 명단이 쓸모 있다 없다 여부를 판단하는 것은 아주 쉬운 문제입니다.

하지만 요주의 인물에 대한 정보가 전혀 없는 직원이 제대로 된 명단을 가져오게 되는 일은 전혀 다른 문제입니다. 우선 130명 가운데 100명을 추려서 만들 수 있는 명단의 개수만 무려 (2 x 10의 29승)개 입니다. 여러분이 1 초에 100만 개의 리스트를 확인할 수 있다고 치고 이 확인 작업을 137억년 전부터 해오고 있다고 하더라도 지금까지 여러분이 작업한 리스트는 전체 가능한 리스트의 0.0002%에 불과합니다.

이렇듯 P vs NP 문제는 “답안을 평가하기 쉬운 문제가 과연 풀기도 쉬운 문제인가?”에 관한 것입니다. 위의 예를 들어서 표현하자면 우리는 어떤 사람이 한 줌 쥐어서 온 건초 더미에 바늘이 있는 지 없는 지 알기는 쉽습니다. 직원이 정성스레 엑셀로 뽑아 가지고 온 명단이 쓸 수 있는 지 없는 지 판단하는 것도 쉽습니다. 하지만 실제로 상암 운동장에 가득 찬 건초 더미에서 바늘을 찾는 일, 셀 수도 없이 많은 조합이 있는 기숙사 합격자 명단 조합에서 쓸 수 있는 명단을 직원이 엑셀로 출력해서 여러분에게 가져오는 일도 과연 쉬운가? 하는 질문이라 하겠습니다.

위의 예를 봤을 때 직관적인 대답은 “아니다”인 것 같습니다.
하지만 아직까지 어떤 누구도 “위의 문제들을 해결할 수 있는 쉬운 해결책은 절대로 없다”라는 것을 수학적으로 증명해 내지는 못했습니다.
우리가 아직까지 알지 못하는 기발한 알고리듬이 있어서 위의 문제의 실제 해결이 맞다 아니다를 판단하는 것 만큼이나 쉽게 이루어 질지도 모르지 않겠습니까?
100% 없다라고 장담하실 수 있나요?

여러분이 이 증명을 해 낸다면 100만 달러(오늘 자 환율로 대략 11억 3천만 원)는 여러분의 것입니다.
도전하세요!!!