토끼 프로그래머 말대로 지뢰를 정확하게 찾으려면 하나씩 확인하는 것이 가장 좋은 방법이야. 그런데 이 방법에도 문제가 있어. 지뢰밭이 커지면 계산해야 할 양이 너무 많아서 컴퓨터가 풀더라도 시간이 오래 걸리거든. 그래서 난 수학자들에게 도움을 요청했지.
컴퓨터가 문제를 풀 때 거쳐야 할 단계의 수가 적을수록 빨리 해결할 수 있겠지? 그래서 크기가 N인 문제를 푸는 알고리듬이 답을 내기까지 거치는 단계를 식으로 나타내서 걸리는 시간을 표현해. 이 식이 N2나 N3-N과 같은 다항식일 때 ‘컴퓨터가 빠르게 풀 수 있다’고 해. 이 식을 ‘다항 시간’이라고 부르지.
그럼 지뢰찾기를 풀려면 컴퓨터로 얼마나 시간이 걸리는지 알아볼까? 지뢰찾기는 토끼가 말한 것처럼 모든 칸을 일일이 확인해 봐야 하기 때문에 N×N 크기의 지뢰밭은 (N2)!의 시간이 걸려. 이를 팩토리얼 시간이라 부르는데, 컴퓨터로 계산해도 시간이 오래 걸려. 우리가 초급이라고 여기는 9×9크기의 지뢰찾기를 해결하려면, 컴퓨터는 약 5.80×10120번의 계산을 해야 하거든. 그렇기 때문에 우리는 일일이 열어보지 않고 더 쉽게 지뢰를 찾을 수 있는 알고리듬을 찾아야만 해. 이 알고리듬이 과연 존재할까?
이 문제가 바로 인간 세계에서 유명한 난제인 ‘P 대 NP 문제’야. P다, NP다 새로운 용어가 나오니까 복잡한 표정을 짓는데, 이미 다 아는 내용이니 겁먹지 말라고. 앞에서 설명했거든. 컴퓨터가 빠르게 해결할 수 있는 문제를 P 문제라 하고, 정답을 안다면 그 정답이 맞는지 빠르게 확인할 수 있는 문제를 NP 문제라 하지. P 문제는 정답도 빠르게 확인할 수 있겠지? 그래서 NP 문제에 속해.
하지만 NP 문제 중에는 아직 빠르게 정답을 찾는 방법을 몰라서 P 문제인지 아닌지 모르는 문제가 있어. P 대 NP 문제는 바로 이런 NP 문제들이 모두 P 문제인지 아닌지 증명하는 거야. 만약 모든 NP 문제가 P 문제라면 문제의 답이 맞는지 빠르게 확인할 수 있는 문제는 빠르게 푸는 방법이 있을테고, 다르다면 문제의 답이 맞는지 빠르게 확인할 수는 있어도 답을 빠르게 푸는 방법은 없을 수도 있다는 의미가 되지. 이 문제는 미국 클레이수학연구소에서 100만 달러(약 11억 6000만 원) 상금을 내건 ‘밀레니엄 문제’ 중 하나야.
수학자들은 이 문제를 풀기 위해 아직 P 문제라고 밝혀지지 않은 NP 문제 중 ‘NP 완전문제’라는 것을 골라내지. NP 완전문제 중에 단 하나라도 P 문제라는 것이 밝혀지면 P=NP라는 연구가 있었거든.
1999년 수학자 리차드 케야 영국 버밍엄대학교 수학과 교수는 지뢰찾기 문제가 NP 완전문제라는 사실을 밝혔어. NP 완전문제는 다항 시간 안에 P가 아닌 NP 문제를 다른 P가 아닌 NP 문제로 바꿀 수 있는 문제를 말해. 지뢰찾기는 지뢰가 어디 있는지 안다면 피해서 칸을 고를 수 있지만 모르는 상황에선 해결하기 어려운 문제인 NP 문제이면서, 이 문제가 P 문제라는 것을 증명하면 모든 ‘P=NP’임을 증명할 수 있는 특별한 NP 완전문제라는 거지. 결국 우리의 생사의 문제는 수학계에 위대한 난제이기도 한 거야!
