슈퍼마리오 레벨을 클리어하는 게 수학적으로 NP-hard 문제와 동치라는 논문이 있다. MIT를 비롯한 여러 대학 연구자들이 실제로 증명해냈다. 황당하다고 느끼는 게 정상이다. 근데 이 발견이 컴퓨터 과학에서 수십 년째 아무도 못 풀고 있는 최대 난제와 직결된다. P vs NP 문제다.
복잡도란 ‘어려움의 등급’이다
컴퓨터 과학에서 ‘복잡도(complexity)’는 코드가 복잡하냐의 문제가 아니다. 입력 크기가 커질수록 시간과 자원이 얼마나 빠르게 늘어나는지를 보는 개념이다.
100개짜리 리스트를 정렬하는 건 빠르다. 그 알고리즘으로 1,000,000개를 정렬하면? 성능 차이가 선형적(O(n))이냐 기하급수적(O(2^n))이냐에 따라 실제로 쓸 수 있는 알고리즘인지 아닌지가 완전히 갈린다. 이론이 아니라 현실 얘기다.
여기서 두 클래스가 나온다.
- P (Polynomial time): 다항식 시간 안에 풀 수 있는 문제. 컴퓨터가 빠르게 답을 낸다.
- NP (Nondeterministic Polynomial time): 답이 주어지면 다항식 시간에 검증은 되는데, 직접 푸는 건 아직 느린 문제들.
핵심 질문이 바로 이거다. P = NP인가? 즉, “답 확인이 빠른 모든 문제는 풀기도 빠른가?” 아직 아무도 모른다. 밀레니엄 수학 7대 난제 중 하나고, 증명하면 상금이 100만 달러다. 수십 년째 빈 봉투다.
NP-hard, 이게 가장 무거운 등급이다
NP-hard는 NP에 속하는 모든 문제보다 최소한 같거나 더 어려운 문제들을 묶은 클래스다. 교과서에 단골로 나오는 예시가 셋 있다.
- 외판원 문제(Travelling Salesman Problem): n개 도시를 전부 한 번씩 방문하는 최단 경로 찾기
- 배낭 문제(Knapsack Problem): 무게 제한이 있는 배낭에 가치 합계를 최대로 담는 물건 선택
- SAT 문제: 논리식을 참으로 만드는 변수 조합 찾기
공통점은 하나다. 입력이 조금만 커지면 완전 탐색(brute force)으로는 우주 나이보다 오래 걸린다. 그래서 실전에서는 근사 알고리즘이나 휴리스틱으로 버틴다. 완벽한 답이 아니라 “충분히 괜찮은 답”을 구하는 방식이다.
슈퍼마리오가 NP-hard인 이유
MIT를 비롯한 여러 대학 컴퓨터 과학자들이 슈퍼마리오 브라더스 레벨 클리어 가능성 판단 문제가 NP-hard임을 수학적으로 증명했다. 접근법이 꽤 기발하다. 레벨을 논리 회로로 변환하는 방식이다.
마리오가 특정 경로를 지나는지 여부를 AND 게이트, OR 게이트처럼 표현하는 구조가 성립한다. 파이프, 적, 블록의 배치가 논리 연산을 수행하도록 설계되면, 그 레벨을 클리어하는 방법을 찾는 게 SAT 문제를 푸는 것과 구조적으로 같아진다. 솔직히 처음 이 논문을 봤을 때 “이게 진짜 연구야?” 싶었는데, 엄연한 수학적 증명이다.
결국 임의의 슈퍼마리오 레벨이 클리어 가능한지 판단하는 알고리즘은 이론상 NP-hard다. 사람은 직관과 경험으로 빠르게 풀어내는 것처럼 보이지만, 컴퓨터가 보편적으로 처리하기엔 구조 자체가 극도로 어렵다. 마리오만이 아니다. 테트리스, 포켓몬, 젤다의 전설 시리즈도 같은 분석을 받았다.
그래서 현실에서 뭐가 달라지나
“게임이 NP-hard면 나한테 무슨 상관이야”라고 생각할 수 있다. 생각보다 파장이 있다. 세 가지만 짚는다.
첫째, AI 게임 플레이어 개발 난이도를 설명해준다. 구글 딥마인드가 알파고로 바둑을 정복했지만, 슈퍼마리오처럼 복잡한 레벨 구조의 게임에서 AI가 고전하는 이유 중 하나가 이 계산 복잡도 구조다. 모든 경우를 탐색할 수 없으니, 강화학습으로 근사치를 찾는 방식을 쓸 수밖에 없다.
둘째, 레벨 디자인 자동화에 이론적 한계가 있다. AI로 게임 레벨을 자동 생성하는 기술이 발전하고 있지만, 최적 레벨인지 검증하는 것 자체가 NP-hard다. 완전 자동화에는 벽이 있다는 뜻이다. 이건 좀 아이러니하다 — 만들 수는 있어도 최적인지 확인하기가 더 어렵다.
셋째, 알고리즘 교육에서 강력한 도구가 된다. 추상적인 P/NP 개념을 게임으로 설명하면 체감 속도가 다르다. 코딩 교육에서 게임 기반 학습 효과가 꾸준히 연구로 나오는 것도 이 맥락이다.
P vs NP를 파고 싶다면, 이 순서로
흥미가 생겼다면 진입 경로가 몇 가지 있다. 수준별로 골라도 된다.
- 《Introduction to the Theory of Computation》 by Michael Sipser — 계산 이론의 교과서. 복잡도 이론을 처음부터 체계적으로 다룬다.
- Scott Aaronson의 블로그 ‘Shtetl-Optimized’ — MIT 교수가 직접 운영하며, 계산 복잡도를 일반인도 따라갈 수 있게 풀어쓴다.
- Coursera의 ‘Algorithms’ 시리즈(Stanford) — Tim Roughgarden 교수 강의로, 복잡도 이론 파트가 포함돼 있다.
- 코딩테스트 플랫폼(BOJ, LeetCode) — NP-hard 문제를 직접 근사적으로 풀어보는 게 체감상 가장 빠르다. 이론보다 손이 먼저다.
수학 배경이 없어도 개념 이해는 된다. 증명까지 파고들려면 이산수학과 집합론 기초가 있으면 좋지만, “왜 어떤 문제는 컴퓨터로도 빠르게 못 푸는가”라는 감을 잡는 데는 진입 장벽이 높지 않다. 일단 시작해보면 안다.
게임 속에 수학이 숨어 있었다
어린 시절 거실에서 조이스틱을 잡으며 무의식적으로 다루던 구조 속에, 수십 년째 전 세계 수학자들이 매달려 있는 문제가 숨어 있었다. 이상한 얘기 같지만 사실이다.
P vs NP 문제가 풀리지 않는 한, 슈퍼마리오 레벨 클리어 가능성을 판단하는 알고리즘은 이론상 완벽하게 효율적일 수 없다. 그 사실이 오히려 게임을 더 흥미로운 연구 대상으로 만든다. 컴퓨터 과학의 핵심 개념들이 게임, 퍼즐, 일상 문제에서 영감을 받아 발전해 온 건 우연이 아니다. 좋은 문제는 늘 의외의 곳에 있었다.