1. 2021년 7월 19일 월요일. 여느 때처럼 코로나19로 어수선하던 여름날, 복잡계 이론의 대가인 한 컴퓨터 과학자가 한 학술지에서 일어난 논쟁에 관한 공개 트윗을 올렸다. 그는 묵직한 한 마디를 남기며 끝맺었다.

“행복한 월요일(Happy Monday)”

이 세상이 아닌 평행 우주 어딘가였다면 분명 행복에 겨운 월요일이었을지도 모른다. ‘실현 가능한 계산의 한계를 탐구하는 뛰어나고 독창적인 연구’를 다루는 학술지인 <ACM(Association for Computing Machinery)>의 컴퓨터계산 이론 분과(Transactions on Computational Theory, TOCT)에 한 증명이 온라인으로 게시되었다. 그 증명은 결과적으로 최고 난제 하나를 해결할 수 있다고 주장했다. 풀기만 한다면 아리스토텔레스에 필적하는 명성을 얻고, 100만 달러(약 12억 원)의 상금까지 거머쥘 수 있는 이론 컴퓨터 과학 분야에 있어 성배(聖杯)로 여겨진 문제였다.

일명 ‘P 대 NP’라고 알려진 이 유명한 난제는 이론 컴퓨터학과 수학 분야에서 가장 중요한 난제로 여겨진다. 이 문제는 다음과 같은 질문을 통해 계산의 가능성, 한계 및 목표에 핵심적인 의문을 제기한다.

• 왜 어떤 문제는 다른 문제보다 더 어려운가?

• 컴퓨터가 현실적으로 해결할 수 있는 문제는 무엇인가?

• 해결이 얼마나 오래 걸릴 것인가?

이는 철학적으로 중요하고 실용적으로도 가치 있는 연구다.