유니크 게임 추측 증명 경쟁 — 민저 팀 4대1 증명과 OpenAI 발표 총정리

📐 수학 이야기

유니크 게임 추측은 2002년 서브하시 코트가 제기한 계산 복잡도의 난제다. 유니크 게임 추측과 2대1 추측의 뜻, MIT 민저 팀의 95쪽 4대1 증명, 2026년 10월 6일 OpenAI 발표와 검증 상태를 정리했다.

2026년 9월 MIT의 도어 민저와 대학원생 두 명이 유니크 게임 추측의 사촌 격인 2대1 추측의 약한 형태, 이른바 4대1 버전을 증명한 95쪽짜리 논문을 올렸다. 10월 6일에는 OpenAI가 유니크 게임 추측 증명을 포함한 결과를 발표했다고 퀀타 매거진이 전했다. 유니크 게임 추측이 무엇이고 왜 중요한지 정리한다.

유니크 게임 추측이란 무엇인가요?

유니크 게임 추측은 그래프의 꼭짓점에 정해진 색 팔레트에서 색을 하나씩 칠하는 문제로 설명된다. 각 변은 양 끝점의 색이 서로 어떤 규칙을 만족해야 한다는 제약을 걸고, 유니크라는 이름은 한쪽 색이 정해지면 다른 쪽 색이 정확히 하나로 정해진다는 데서 왔다. 이 추측은 서브하시 코트가 2002년 대학원생 시절 논문에서 제기했다.

추측의 내용은 이렇다. 제약의 99%를 만족하는 칠하기가 존재하는 문제라도, 제약의 아주 작은 비율이라도 만족하는 칠하기를 찾는 것은 어렵다는 것이다. 어렵다는 말은 계산 복잡도 이론에서 효율적인 알고리즘이 없다는 뜻으로 쓰인다.

$$\text{UGC: } \forall \varepsilon,\delta>0,\ \text{ 만족 비율 } \ge 1-\varepsilon \ \text{ 대 } \ \le \delta \ \text{ 를 구별하는 것은 어렵다}$$

유니크 게임 추측의 직관적 서술: 거의 완벽히 풀리는 경우와 거의 못 푸는 경우의 구별이 어렵다

유니크 게임 추측이 중요한 이유는 무엇인가요?

유니크 게임 추측이 참이면 제약 만족 문제 전반에 대해 프라사드 라그하벤드라가 2008년 보인 고전적 알고리즘이 최선이라는 결론이 따라 나온다. 즉 어떤 근사 알고리즘 하나가 수많은 문제에서 이론적 한계에 닿아 있다는 뜻이다. 그래서 유니크 게임 추측은 근사 알고리즘의 한계를 한꺼번에 설명하는 열쇠로 불려 왔다.

이 추측에는 사각지대가 있다. 유니크 게임 추측은 거의 완벽한 해가 존재하는 경우만 다루고, 완벽한 해가 실제로 존재하는 경우에 대해서는 말하지 않는다. 그 빈틈을 메우려고 코트가 내놓은 것이 2대1 추측이다.

2대1 추측과 4대1 증명은 무엇인가요?

2대1 추측은 변마다 허용되는 색이 하나가 아니라 둘로 느슨해진 제약을 쓴다. 이 추측은 완벽한 해가 존재하는 문제 중에서도 제약의 작은 비율을 만족시키는 일조차 쉽지 않은 경우가 있다고 주장한다. 2018년 대학원생이던 민저가 유니크 게임 추측으로 가는 길의 이정표를 세운 이래 이 문제가 후속 연구의 중심에 있었다.

2026년 9월 민저와 대학원생 Yumou Fei, Shuo Wang은 허용되는 색이 둘이 아니라 넷인 4대1 버전을 증명한 95쪽 논문을 전자 계산 복잡도 논문 저장소 ECCC에 올렸다. 4대1 버전은 약간 약한 형태지만 유니크 게임 추측의 결과 대부분을 함의한다. 대표적으로 3색으로 칠할 수 있는 그래프에서도 색을 몇 개 더 허용해 칠하라고 해도 효율적으로 찾을 방법이 없다는 결과가 따라온다.

4대1 증명 관련 확인된 사실

• 증명자: 도어 민저(MIT)와 대학원생 Yumou Fei, Shuo Wang
• 분량: 95쪽, ECCC에 자체 게재 (동료 심사 전)
• 시기: 핵심 돌파는 2026년 4월, 논문 게재는 9월
• 저자들은 논문이 수학적으로 완결됐지만 원하던 형태는 아니라고 첫 쪽에 밝혔다

OpenAI의 발표는 어떻게 봐야 하나요?

2026년 9월 11일 OpenAI가 유니크 게임 추측 결과를 낸다는 소문이 돌자 민저 팀은 논문을 서둘러 올렸다고 퀀타 매거진은 전했다. 10월 6일 OpenAI는 유니크 게임 추측 증명을 포함해 수학 분야의 다른 376개 결과를 함께 발표했다. 이 발표에는 2대1 추측을 증명한 AI 생성 원고와 정형 검증 언어 린으로 검증했다는 증명이 포함됐다.

다만 퀀타 보도 시점에 OpenAI의 원고는 사람의 편집이나 독립 전문가의 검토를 거치지 않은 상태였다. 린 검증은 증명의 논리 단계가 기계적으로 맞는지를 확인하지만, 명제가 원래의 추측과 정확히 같은지는 사람이 확인해야 한다. 그래서 유니크 게임 추측이 해결됐다고 단정하기에는 이르고, 커뮤니티의 검증을 기다리는 단계로 보는 것이 신중한 읽기다.

정리하면 유니크 게임 추측은 아직 공식적으로 해결되지 않았다. 민저 팀의 4대1 증명과 OpenAI의 AI 생성 증명 모두 독립 검증이 진행 중이고, 확정 여부는 후속 심사 결과에 달려 있다.

유니크 게임 추측 소식을 정리하며

이번 소식에서 가장 흥미로웠던 점은 유니크 게임 추측이라는 순수 이론 문제가 사람 연구팀과 AI가 사실상 같은 시기에 결승선에 다가선 경쟁 구도로 보도됐다는 것이다. 개인적으로는 7년에 걸친 사람의 연구와 단기간의 AI 증명이 어떻게 검증되고 평가받는지가, 유니크 게임 추측의 결과 못지않게 앞으로 수학계가 정리해야 할 문제라고 느꼈다. 유니크 게임 추측의 최종 판정은 전문가 검증이 끝난 뒤에 확인해야 한다.

함께 읽으면 좋은 글

오픈AI 유니크 게임 추측 증명 주장 — P NP 문제 예시와 뜻 총정리이항분포 뜻과 공식, 평균·분산 유도와 예제 정리평균과 중앙값 차이, 평균 소득이 체감과 다른 이유

참고 자료

Quanta Magazine — As AI Closed In on Unique Games Proof, Researchers Raced to Beat the MachinesECCC — Electronic Colloquium on Computational ComplexityWikipedia — Unique games conjecture