유일 게임 추측

최적설계 수치해석 마지막 수정: 2026-08-19 04:51:19

1. 개요[편집]

유일 게임 추측 Unique Games Conjecture (UGC)
제기	Subhash Khot (2002)
내용	유일 제약 CSP에서 값 $\ge 1-\varepsilon$ 대 값 $\le \delta$ 판별이 NP-난해라는 추측
상태	미해결 — 참·거짓 모두 미증명
주요 귀결	MAX-CUT의 $0.878\ldots$ 근사가 최적 · 정점 덮개 $2-\varepsilon$ 불가
일반 정리	Raghavendra (2008) — 모든 CSP에서 기본 SDP가 최적
반대 방향	Arora–Barak–Steurer (2010) 준지수시간 알고리즘
부분 진전	2-대-2 게임 정리 (Khot–Minzer–Safra, 2018)

유일 게임 추측(Unique Games Conjecture, UGC)은 “유일 제약”만으로 이루어진 제약 충족 문제에서, 거의 전부 만족되는 인스턴스와 거의 아무것도 만족되지 않는 인스턴스를 구별하는 것조차 NP-난해하다는 추측이다. 2002년 수바시 코트가 제기했으며, 지금도 참인지 거짓인지 아무도 모른다.

문제 설정부터 보자. 유일 게임(unique game) 인스턴스는 다음으로 주어진다.

그래프 $G = (V, E)$ — 변수와 제약
알파벳 $[k] = \{1, \dots, k\}$ — 각 변수가 가질 수 있는 라벨
간선 $e = (u,v)$ 마다 전단사 $\pi_e : [k] \to [k]$

라벨 배정 $\ell: V \to [k]$ 가 간선 $e$ 를 만족한다는 것은 $\pi_e(\ell(u)) = \ell(v)$ 인 것이다. 유일이라는 이름은 여기서 나온다 — 한쪽 라벨을 정하면 다른 쪽 라벨이 유일하게 결정된다. 인스턴스의 값 $\mathrm{val}$ 은 만족되는 간선의 최대 비율이다.¹

\textbf{UGC: } \forall \varepsilon, \delta > 0,\ \exists k \text{ such that } \big[\ \mathrm{val} \ge 1-\varepsilon\ \big] \text{ vs } \big[\ \mathrm{val} \le \delta\ \big] \text{ 판별이 NP-난해}

이 추측이 이례적인 것은, 추측 자체보다 그것이 낳는 귀결의 목록이 훨씬 유명하다는 점이다. 최적화 문제 수십 개에서 “현재 최선의 다항시간 알고리즘이 사실은 최적이다”라는 결론이 UGC 하나에서 줄줄이 따라 나온다. 근사 알고리즘 연구자에게 UGC는 “더 잘하려고 애쓰지 말라”는 전언이자, 동시에 반증되면 판이 뒤집히는 도박이다.²

2. 왜 $1$ 이 아니라 $1-\varepsilon$ 인가[편집]

완전성 조건이 $1-\varepsilon$ 이지 $1$ 이 아니라는 점은 장식이 아니라 필수다. 값이 정확히 $1$ 인 유일 게임(= 모든 제약을 만족하는 배정이 존재)은 다항시간에 풀린다. 연결 성분 하나에서 아무 변수의 라벨을 $k$ 가지로 다 시도해 보면, 유일성 때문에 나머지 라벨이 전파로 전부 결정되기 때문이다. 성분마다 $O(k \cdot |E|)$ 면 끝난다.

즉 유일 게임은 완전 만족 가능한 경우가 쉬운 문제이고, UGC는 “ $1$ 에서 $\varepsilon$ 만 떨어지는 순간 절벽이 있다”는 주장이다. 이 구조가 PCP 정리 계열의 다른 난해성 결과들과 결정적으로 다른 점이다 — 예컨대 3-SAT의 갭 버전은 완전 완전성(perfect completeness)을 유지한 채 난해하지만, 유일 게임은 그럴 수 없다. 그래서 UGC를 증명하려는 모든 시도는 완전성을 잃는 대가를 어디선가 치러야 하고, 이 지점이 20년 넘게 병목이었다.

3. 귀결 1 — MAX-CUT과 0.878[편집]

최대 절단(MAX-CUT)은 정점을 두 편으로 갈라 양편을 잇는 간선 수를 최대화하는 문제로, NP-난해의 원형 중 하나다. 괴만스와 윌리엄슨(1995)의 반정부호 계획법 완화는 각 정점 $i$ 에 단위벡터 $\mathbf{v}_i$ 를 배정하고

\max \ \sum_{(i,j) \in E} \frac{1 - \mathbf{v}_i \cdot \mathbf{v}_j}{2}

를 푼 뒤, 무작위 초평면으로 벡터를 두 편으로 가른다. 두 벡터가 각 $\theta$ 만큼 벌어져 있으면 갈릴 확률이 $\theta/\pi$ 이고 완화 목적값 기여가 $(1-\cos\theta)/2$ 이므로, 근사비는

\alpha_{\mathrm{GW}} \;=\; \min_{0 < \theta \le \pi} \frac{2}{\pi} \cdot \frac{\theta}{1 - \cos\theta} \;\approx\; 0.87856

가 된다. 30년 넘게 아무도 이 상수를 넘기지 못했고, 하필 값이 $0.878\ldots$ 라는 아무 의미 없어 보이는 숫자여서 “이건 분명 최적이 아니고 더 나은 알고리즘이 있을 것”이라는 정서가 오래 있었다.

코트·킨들러·모셀·오도넬(2004/2007)이 UGC 하에서 이 정서를 뒤집었다. UGC가 참이면 임의의 $\varepsilon>0$ 에 대해 $\alpha_{\mathrm{GW}} + \varepsilon$ 근사가 NP-난해다. 증명의 해석학적 심장은 최다득표가 가장 안정적(Majority is Stablest) 정리로, 모셀·오도넬·올레슈키에비치(2005/2010)가 가우스 등주부등식과 불변 원리로 증명했다. 요지는 “각 좌표의 영향력이 작은 불 함수 중 잡음 안정성이 가장 높은 것은 다수결”이며, 이 함수해석 결과가 그대로 UGC 기반 환원의 사영 검사(dictatorship test)로 번역된다.

UGC 없이 알려진 최선은 하스타드 계열의 $16/17 \approx 0.941$ 이다. 즉 $0.878$ 과 $0.941$ 사이의 간극을 메우는 것이 UGC의 역할이다.

수치해석 쪽에서 MAX-CUT이 익숙한 이유도 있다. 절단값 최대화는 반강자성 이징 모형의 바닥 상태를 찾는 것과 같은 문제이며, 스핀글라스의 기저 에너지 계산이 곧 가중 MAX-CUT이다. GW 완화는 스핀 $\sigma_i = \pm 1$ 을 고차원 단위벡터로 풀어 준 뒤 무작위 사영으로 되돌리는 것으로, 물리 쪽 관점에서는 자연스러운 완화다. 실제 SDP는 내점법이나 저계수 버-몬테이로 방식으로 푼다.

4. 귀결 2 — 정점 덮개 $2-\varepsilon$ [편집]

최소 정점 덮개에는 초등적인 2-근사가 있다. 아무 극대 매칭이나 잡아 양 끝점을 전부 넣으면 되고, 이건 학부 첫 학기 내용이다. 반세기 동안 이 상수를 $2 - c/\sqrt{\log n}$ 정도로 아주 조금 깎은 것 외에 진전이 없었다.

코트와 레게브(2003/2008)는 UGC 하에서 임의의 $\varepsilon > 0$ 에 대해 $2-\varepsilon$ 근사가 NP-난해임을 보였다. 즉 그 초등적 알고리즘이 이미 최적이라는 것. UGC 없이 알려진 하한은 디누어·사프라(2005)의 $1.3606$ 이었고, 2018년 2-대-2 게임 정리가 이를 $\sqrt{2} \approx 1.4142$ 까지 올렸다.

5. 귀결 3 — 라구벤드라의 일반 정리[편집]

개별 문제를 하나씩 처리하는 것이 아니라 한 방에 전부 처리해 버린 것이 라구벤드라(2008)의 결과다.

UGC가 참이면, 임의의 제약 충족 문제에 대해 그 문제의 기본 SDP 완화가 달성하는 근사비보다 나은 다항시간 근사는 NP-난해하다.

이건 개별 정리가 아니라 메타 정리다. MAX-CUT, MAX-2SAT, MAX-DICUT 등 각 CSP마다 최적 근사비가 “그 CSP의 SDP 적분성 간극”이라는 하나의 양으로 통일된다. 근사비의 정확한 값이 닫힌 형태로 안 나올 수도 있지만(대개 어떤 최적화 문제의 최적값으로만 기술된다), 어디를 봐야 하는지는 완전히 결정된다.

이 결과가 근사 알고리즘 분야에 준 충격은 컸다. CSP에 관한 한 “새 알고리즘을 발명할 여지”가 UGC 하에서 통째로 사라지고, 남는 일은 기본 SDP를 잘 푸는 것과 그 적분성 간극을 계산하는 것뿐이 된다. 물론 CSP가 아닌 문제(외판원 문제류의 순서·연결성 제약 문제 등)는 이 우산 밖에 있다.³

6. 반대 방향 — 준지수시간 알고리즘[편집]

UGC를 의심할 근거도 만만치 않다. 아로라·바락·스티어러(2010)는 유일 게임에 대한 준지수시간(subexponential) 알고리즘을 냈다. 고정된 $\varepsilon$ 에 대해 실행시간이 대략 $\exp\!\left(k\, n^{\varepsilon}\right)$ 형태라, 지수의 지수가 $1$ 보다 작아 진짜 지수시간보다 훨씬 빠르다. 대신 구별해 내는 갭이 $\varepsilon$ 에 따라 좁아지므로 UGC를 직접 무너뜨리지는 못한다. 알고리즘의 뼈대는 그래프 라플라시안의 작은 고유값 개수를 세는 스펙트럼 논증 — 고유값이 작은 방향이 적으면 문제를 낮은 차원으로 접어 완전탐색할 수 있고, 많으면 그래프를 잘라 재귀한다.

이것이 UGC를 반증하지는 않는다. NP-난해 문제 중에도 준지수시간에 풀리는 것이 있을 수 있으니까. 다만 UGC를 증명하려는 환원은 반드시 인스턴스 크기를 크게 부풀려야 한다는 구조적 제약을 준다. 3-SAT에서 시작해 크기를 거의 유지하는 환원으로 UGC를 얻으려는 시도는 이 알고리즘과 지수시간 가설에 함께 가로막힌다. 실제로 이 결과 이후 “UGC는 아마 거짓일 것”이라는 견해가 늘었다가, 2018년 진전으로 다시 분위기가 반대로 흘렀다.

같은 시기 라구벤드라와 스티어러(2010)는 소집합 확장 문제(Small-Set Expansion, SSE)를 정식화했다. 정규 그래프에서 작은 정점 집합의 확장률이 거의 $1$ 인지 거의 $0$ 인지 구별하는 문제이며, SSE 가설이 참이면 UGC도 참임을 보였다. UGC의 어려움이 사실은 확장 그래프 구조의 어려움이라는 재해석이며, 유일 게임 인스턴스의 난이도가 제약의 조합적 성질보다 그래프의 스펙트럼적 성질에 달려 있음을 시사한다. 준지수시간 알고리즘이 스펙트럼 논증인 것도 우연이 아니다.

증명 전략 하나는 일찌감치 막혔다. 2-프루버 게임의 난해성을 키우는 표준 도구인 병렬 반복을 유일 게임에 쓰면 유일성이 깨지고, 유일성을 보존하는 강한 병렬 반복은 라즈(2008)가 홀수 사이클 게임으로 반례를 만들어 불가능함을 보였다. 손쉬운 증폭 경로가 없다는 뜻이다.

7. 2018년 — 2-대-2 게임 정리[편집]

간선 제약이 전단사가 아니라 2-대-2 대응(각 라벨이 상대편 라벨 2개와 짝지어짐)인 완화판을 2-대-2 게임이라 한다. 코트·민저·사프라(2018)가 불완전 완전성을 갖는 2-대-2 게임 추측을 증명했다. 디누어·킨들러가 합류한 연작과 바락·코타리·스티어러의 기여가 얹힌 여러 편짜리 프로그램의 종착점이었고, 마지막 조각은 그라스만 그래프의 유사난수 집합이 거의 완벽한 확장성을 갖는다는 조합적 명제였다.⁴

여기서 따라 나오는 것은

유일 게임에서 $\big[\mathrm{val} \ge \tfrac12 - \varepsilon\big]$ vs $\big[\mathrm{val} \le \varepsilon\big]$ 판별이 NP-난해. 완전성이 $1-\varepsilon$ 이 아니라 $\tfrac12$ 이라는 점에서 UGC의 절반에 해당한다.
정점 덮개의 $\sqrt{2} - \varepsilon$ 근사가 NP-난해. 디누어·사프라의 $1.3606$ 을 넘어선 첫 개선이다.
독립집합 쪽으로는, 독립수가 $(1-\tfrac{1}{\sqrt2})n$ 이상인지 아니면 자명한 크기뿐인지 구별하는 것이 NP-난해라는 형태로 나온다.

남은 것은 완전성을 $\tfrac12$ 에서 $1-\varepsilon$ 으로 끌어올리는 일이고, 이게 전혀 형식적이지 않다. 그래도 “UGC 방향으로 진짜 벽돌 하나가 놓였다”는 데는 이견이 없으며, 코트는 이 계열 업적으로 2014년 네반린나상을 받았다.

8. 지금 어디까지 왔나[편집]

참인지 거짓인지 모른다. 2-대-2 정리 이후 참 쪽으로 기운 사람이 늘었지만 합의는 없다.
제곱합(Sum-of-Squares, SoS) 위계가 유력한 반증 도구로 남아 있다. 바락 외(2012)가 기존에 알려진 UG 적분성 간극 인스턴스들이 상수 차수 SoS로 풀린다는 것을 보였다. 즉 지금까지 사람이 만든 “어려운 예제”는 전부 SoS 앞에서 무너졌다. 진짜 어려운 인스턴스가 있다면 아직 아무도 못 만든 것이거나, 없는 것이거나.
실무적 함의는 이미 발생했다. UGC의 참·거짓과 무관하게, “기본 SDP 완화 + 무작위 반올림”이 CSP 근사의 사실상 표준 도구가 됐다. 라구벤드라 정리는 그 관행에 이론적 정당성을 얹어 준 셈이고, 정수계획법 솔버가 절단면을 얹는 것과 SDP 위계를 올리는 것 중 어디에 투자할지의 판단 근거도 여기서 나온다.

9. 관련 문서[편집]

“게임”이라는 단어는 상호작용 증명 쪽 용어를 물려받은 것이다. 검증자가 두 증명자에게 각각 질문을 던지고 답이 서로 정합적인지 확인하는 2-프루버 1-라운드 게임에서, 한 증명자의 답이 다른 증명자의 답을 유일하게 결정하는 특수한 경우가 유일 게임이다. 그래서 코트의 2002년 논문 제목도 “유일 2-프루버 1-라운드 게임의 힘에 관하여”다. 정작 지금은 대부분 그냥 라벨 붙이기 문제로 서술한다. ↩
“P $\ne$ NP를 가정하면 X는 어렵다”와 “UGC를 가정하면 X는 어렵다”는 심리적 무게가 다르다. 전자는 사실상 공리 취급이지만 후자는 진짜 도박이다. 그래서 논문 초록에 “assuming the Unique Games Conjecture”라고 정직하게 붙는데, 이 문구가 붙은 정리가 수백 편 쌓여 있다는 사실 자체가 이 바닥에서 UGC가 차지하는 지분을 보여 준다. ↩
라구벤드라 정리의 서술을 처음 보면 “그래서 근사비가 얼마인데?”라고 묻게 되는데, 정리는 그 값을 닫힌 형태로 주지 않는다. 각 CSP마다 정의되는 어떤 최적화 문제의 값이라고만 말한다. MAX-CUT처럼 그 값이 $0.878\ldots$ 로 계산되는 경우가 오히려 예외다. “답은 존재하고 계산 대상도 특정되지만 숫자는 모른다”는 상태가 이론 컴퓨터과학에서는 꽤 흔하다. ↩
그라스만 그래프는 유한체 위 벡터공간의 부분공간들을 정점으로 놓고 교집합 차원이 큰 것끼리 이은 그래프다. 조합적 확장성 명제 하나를 위해 이런 대상이 동원됐고, 증명은 여러 편에 걸쳐 수십 명분의 노동으로 완성됐다. 근사 알고리즘 상수 하나를 확정하려고 유한 기하학까지 끌어오는 게 이 분야의 평범한 일상이다. ↩