d라이브러리

이제 견학이 막바지에 이르렀습니다. 마지막으로 아주 중요하고 어려운 수학 문제를 알려드리겠습니다. 여러분을 이곳으로 데려온 행운의 보물, 골든 티켓을 꺼내주세요. 어떤 방법으로 그 골든 티켓을 찾았나요?

‘찰리와 초콜릿 공장’은 영국의 소설가 로알드 달이 1964년에 발표한 인기 소설입니다. 천재 발명
가이자 세계적인 초콜릿 공장의 주인인 윌리 웡카의 초대를 받은 다섯 명의 아이가 공장을 견학하
면서 벌어지는 이야기를 담고 있죠. 그런데 이 이야기에서 재미만이 아니라 수학계의 중요한 문제까지 찾아낸 사람이 있습니다. 

2013년 랜스 포트노우 미국 조지아공과대학교 컴퓨터과학과 교수는 자신의 책 ‘골든 티켓’에서 찰리와 초콜릿 공장에 빗대어 P대 NP 문제를 설명했습니다. P대 NP 문제는 무엇이고, 소설의 줄거리는 어떻길래 수학으로 설명할 수 있다는 걸까요? 

웡카는 후계자를 찾기 위해 세계로 팔려나가는 초콜릿에 무작위로 다섯 개의 골든 티켓을 집어넣었습니다. 겉에서는 전혀 알 수 없고 어느 나라에 있을지도 알 수 없습니다. 이 수많은 초콜릿 중에서 딱 5개만이 윌리 웡카의 공장에 갈 수 있는 골든 티켓을 품고 있습니다. 

아이들은 저마다의 방법으로 골든 티켓을 찾기 위해 노력했습니다. 그중 부잣집 자식인 베루카 솔트는 부모님의 땅콩 공장 사람들을 총동원해 수많은 초콜릿 박스를 열어 골든 티켓을 찾았습니다. 이 방법은 골든 티켓을 찾는 가장 좋은 방법일까요?

아무리 베루카의 부모님이 부자라고 해도 전세계로 수출된 모든 초콜릿을 확인할 수는 없습니다. 직원들이 1초에 1개씩 초콜릿을 열어본다고 해도 천문학적인 시간이 필요하기 때문입니다. 이렇게 어마어마한 경우의 수가 있을 때 가장 빠르고 비용이 적게 드는 골든 티켓 찾기 방법이 있을까요? 

P=NP 추측을 증명하는 것이 진짜 골든 티켓!

어떤 문제에 대해, 정해진 단계 안에 풀 수 있는 경우를 수학에서는 ‘P’라고 합니다. 반면 답을 구하는 효율적인 알고리듬은 모르지만 풀이 과정을 보면 특정 횟수 안에 답이 옳은지 판별할 수 있는 문제를 ‘NP’라고 합니다. 

만약 P=NP라면 지금은 효율적인 알고리듬을 찾지 못한 문제도 빠른 시간 안에 답을 찾을 수 있는 알고리듬이 존재한다는 뜻이 됩니다. 그러면 베루카도 무작정 모든 초콜릿을 확인하지 않고 꼭 필요한 돈과 인력만 들여서 골든 티켓을 찾을 수 있겠죠. 하지만 P≠NP라면 아무리 돈이 많아도 반드시 확실하게 골든 티켓을 얻을 수 있는 빠른 방법은 존재하지 않습니다. 

P 집합이 NP 집합에 속한다는 것은 증명됐지만, NP 집합이 P 집합에 속하는지는 아직 증명되지 않았습니다. 이 문제는 미국 클레이연구소가 뽑은 7대 난제인 ‘밀레니엄 문제’ 중 하나입니다. 많은 학자가 P≠NP라고 생각하고 있습니다만, 수학적으로 밝혀지지는 않았습니다. 

이 문제가 풀리면 수학계뿐만 아니라 컴퓨터과학, 암호학에도 큰 영향을 미치게 됩니다. 우리 실생활에도 덩달아 많은 변화가 일어나겠죠. 게다가 100만 달러(약 11억 3350만 원)의 현상금도 걸려있으니, 수학을 좋아하는 사람에게는 이 문제를 푸는 것이야말로 행운의 보물 ‘골든 티켓’이라고 할 수 있겠네요. 

7개의 밀레니엄 문제 중 벌써 2개인 나비에-스토크스 방정식 해의 매끄러움 유무와 P대 NP 문제를 초콜릿으로 살펴봤군요. 이쯤 되면 초콜릿이 아니라 ‘수콜릿’이라고 불러야겠습니다.