P와 NP문제

수학의 매력 - 세상의 모든 x값을 찾아 떠나는 여행
리여우화 지음, 김지혜 옮김 / 미디어숲 / 2024년 1월

"만물은 수이다." 고대 그리스의 수학자 피타고라스의 말이다. 과학자와 수학자에게는 십계명 제1조에 해당하는 문구지 싶다. 비록 내 수학지식이 여전히 저공비행의 차원에 머물고는 있지만, 피타고라스의 말에 공감하지 않을 수 없다. 수학자나 물리학자의 전기를 읽다보면, 수학의 아름다움을 찬양한다는 공통점을 발견한다. 비록 수포자 수준이지만, 그런 내게도 수학의 매력을 느끼게 해준 네 가지가 있었다. 165, 오일러 등식, 그리고 원주율 π와 루트2다.

165는 내게 수의 매력을 처음 알려주었다. 165를 계속 더하면 주판을 9999로 계속 채워나갈 수 있기 때문이다. 지금도 그렇지만 주산을 배우지 않은 이들의 연산과 암산은 대체 어떤 식으로 진행되는지 늘 호기심의 대상이다. 난 언제나 주판이 심상으로 그려진 상태에서 연산하기 때문이다. 오일러 등식은 오가와 요코의 소설 《박사가 사랑한 수식》을 통해 처음 접했다. 엄청 감동했지만 오일러 등식을 전혀 이해하진 못했다. 수학계에서 가장 아름다운 등식이라고 소문이 났는데, 이런 수식이야말로 수학자만이 느낄 수 있는 수학의 찐매력인가 어림할 뿐이다. 수학은 정답을 추구하는 증명의 학문으로 유명한데, 원주율 π와 루트2는 끝없는 미완의 신비를 알려주었다. 참, 루트2는 영화 〈이상한 나라의 수학자〉에 등장해 내 호기심을 끌었다.

중국의 수학 마니아 리여우화는 수학 팟캐스트를 운영하며 수학의 대중화와 수학의 문화를 홍보하는 데 앞장서고 있는 IT업계 종사자다. 저서로 《이토록 재미있는 수학이라니》와 《수학의 매력》 등이 있다. 《수학의 매력》 책 표지에 나오는 "수학으로 세상을 이해하는 법"이란 문구와 "여러분에게 수학이 결코 지루한 과목이 아니라 창의성과 재미, 도전성으로 가득 차 있다는 인식을 심어 줄 수 있"다는 UCLA 수학과 교수의 추천사에 혹해서, 본서를 펼쳐 들었다. 내 수준보다 차고 넘치게 어렵다.

최상위 난제의 풀이에는 두둑한 현상금이 붙는다. 일테면 클레이 수학 연구소에서 현상금을 걸고 있는 밀레니엄 7대 수학 난제가 있다. 푸앵카레 추측, P와 NP문제, 호지 추측, 리만 추측, 양-밀스 질량 간극 가설, 나비에-스토크스 방정식 해의 존재성, 버치-스위너턴다이어 추측이다. 이중에서 저자는 알고리즘의 복잡도 문제에서 가장 중요한 'P와 NP문제'에 대해 소개한다. 여기서 P는 다항식의 이니셜이다. 대표적인 P문제는 버블 정렬 같은 정렬 문제와 어떤 정수가 소수인지 아닌지를 판정하는 소수 판정 문제다. 한편, NP문제는 다음과 같다.

"만약 어떤 문제와 이 문제에 대한 어떤 해답이 주어질 때, 다항 시간 알고리즘이 존재하여 이 해답의 정확성을 검증한다면 이 문제는 NP문제이다."(281쪽)

P와 NP문제를 해결하면 백만 달러의 상금을 받을 수 있다고 하니, 여러분이 수학 마니아거나 여러분의 자녀가 수학 천재라면 한번 도전해보면 어떨까.