d라이브러리

멜빵 바지를 입고 빨간 모자를 쓴 콧수염 난 슈퍼마리오의 여정을 게임으로 만든 ‘슈퍼마리오 브라더스’를 아시나요? 여정을 떠난 슈퍼마리오는 머리 위의 벽돌을 점프해서 깨버리고 길 위에 악당이 등장하면 또 점프해서 공격합니다. 다음 단계로 넘어가기 위해서는 악당들을 요리조리 피해 깃대가 있는 곳까지 가야합니다.

그런데 최근 MIT 전기컴퓨터공학과 에릭 드메인 교수팀이 슈퍼마리오 브라더스 게임이 ‘계산 복잡도 단계’에서도 어려운 문제인 ‘PSPACE’만큼 어렵다는 사실을 증명해, 지난 6월 이탈리아에서 열린 ‘재미있는 알고리듬에 관한 국제회의’에서 발표했습니다.

‘계산 복잡도’는 계산 문제를 푸는 알고리듬을 복잡도에 따라 분류해 연구하는 분야입니다. 여기서 P와 NP, NP-하드, PSPACE 등으로 어려운 정도가 나뉘는데, 슈퍼마리오 게임은 매우 어려운 집합에 속하게 되는 것이지요.

연구팀은 2014년, 같은 학회에서 슈퍼마리오 게임이 ‘NP-하드’에 속한다는 사실을 증명했었습니다. 이번에는 화면을 좌표로 나눴을 때 슈퍼마리오의 위치와 시간의 관계를 계산해 NP-하드 문제보다 더 어려운 PSPACE에 속한다는 사실을 밝혀낸 것입니다.

어려운 문제라는 게 증명됐으니 이제 슈퍼마리오 게임을 잘 못한다고 해도 기죽을 필요는 없겠네요.