GPT-5.6과 Dinitz-Garg-Goemans 추측

2026년 7월 22일, Dmitry Rybin은 X에 올린 글로 일부 사람들의 커피를 내려놓게 했습니다. GPT-5.6 Pro가 약 30년 동안 조합최적화 분야에서 열려 있던 Dinitz-Garg-Goemans 추측에 대한 반례를 만들었다는 주장입니다. 개념 증명은 작은 그래프 하나였습니다. 분수 플로우 비용은 58, 분할 불가 플로우 비용은 60. 두 개의 숫자, 세십 년, 네 개의 프롬프트.

대부분의 보도는 이 숫자만 되풀이하고 그 배후의 메커니즘을 보여주지 않는데, 바로 그 메커니즘에 진짜 교훈이 있습니다. 또한 무엇이 검증되었고 무엇이 아직인지 솔직하게 짚어야 하는 부분이기도 합니다. 짧은 버전: 개념은 탄탄하며, 소식은 정리된 정리가 아니라 어디까지나 주장입니다. 그리고 처음부터 똑같은 그래프를 재현하려고 앉아보면, 복원이 새기 시작하는 순간 이런 문제가 왜 어려운지 몸소 알게 됩니다.

빠른 요약

Rybin에 따르면, 60단어가 채 안 되는 네 개의 프롬프트로 유도된 GPT-5.6 Pro가 1999년 무렵부터 열려 있던 Goemans의 비용 추측에 대한 반례를 만들었다고 합니다. 그 인스턴스는 단일 소스와 세 개의 수요 터미널이 있는 작은 유향 그래프입니다. 그는 분할 가능(분수) 라우팅 비용이 58이고, 허용된 혼잡 예산을 지키는 모든 분할 불가 라우팅은 최소 60의 비용이 든다고 말합니다. 그 두 점의 격차가 형식적 검토를 통과한다면, 추측을 무너뜨리기에 충분합니다.

아직 동료 평가를 거치지 않았습니다. Rybin은 누구나 구성을 읽어볼 수 있도록 전체 ChatGPT 대화를 공개했고, 여러 사람이 그의 산술을 확인해 일관적이라고 했습니다. 그러나 재현 가능한 산술과 승인된 증명은 다른 문제이며, 그 사이의 거리가 바로 이 글의 핵심입니다.

Dinitz-Garg-Goemans 추측이란?

무엇이 무너졌는지, 혹은 무너졌을지 이해하려면, 추측이 실제로 무엇을 말하는지 알아야 합니다.

도로망을 통해 창고가 세 개의 마을로 주문을 배송한다고 상상해 보세요. 화물을 분할할 수 있다면, 주문의 절반을 한 도로로, 나머지 절반을 다른 도로로 보낼 수 있습니다. 이것이 분수 라우팅이며 유연합니다. 대개 더 저렴한 경로 집합을 찾죠. 하지만 실제 화물은 분할할 수 없는 경우가 많습니다. 한 주문, 한 트럭, 한 도로, 시작부터 끝까지. 이것이 분할 불가 플로우이며, 실제 화물 주문, 네트워크 패킷, 컨테이너가 해야 하는 일입니다.

1999년부터 사람들이 붙잡고 고민해 온 질문은 간단히 말할 수 있습니다. 저렴한 분할 가능 라우팅이 존재한다면, 도로 과부하를 심하게 일으키지 않으면서 역시 저렴한 분할 불가 라우팅을 항상 찾을 수 있을까요?

Yefim Dinitz, Naveen Garg, Michel Goemans는 그중 절반을 해결했습니다. GPT-5.6이 겨냥한 것은 나머지 절반입니다. 그 구분이 왜 매우 중요한지 이해하려면 정확히 짚고 넘어가야 합니다.

정리(정리된 명제) vs. 추측

많은 글이 이 구분을 흐리니, 여기서 한 번 정확히 설명하고 이후 글 전반에서 그 구분을 전제로 하겠습니다.

Dinitz, Garg, Goemans는 혼잡에 관한 결과를 증명했습니다. 주어진 유효한 분수 플로우를, 어떤 도로의 용량도 가장 큰 수요(이를 D라 합시다)만큼을 초과하지 않도록 하면서 분할 불가 플로우로 항상 변환할 수 있다는 것입니다. 이 정리는 의심받은 적도, 지금도 의심받지 않습니다.

Goemans가 별도로 추측한 것은 더 강한, 비용을 고려한 버전입니다. 같은 변환이 혼잡을 억제하는 동시에 총비용도 낮게 유지될 수 있다는 주장입니다. 혼잡과 비용을 모두 억제하는 하나의 라우팅. 혼잡만 다루는 정리는 안전합니다. 비용+혼잡을 동시에 다루는 추측이 Rybin이 무너졌다고 말하는 부분입니다. 이 글에서 한 문장만 가져가신다면 이 문장입니다. 많은 흥분된 보도가 둘을 슬며시 바꿔 쓰는데, 그 차이가 바로 30년 동안 이어진 수학적 간극 전체입니다.

GPT-5.6이 실제로 만든 것

Rybin의 인스턴스는 단락 하나로 묘사할 수 있을 만큼 작습니다. 하나의 소스, 공유된 "척추"를 이루는 몇 개의 중간 노드, 그리고 각각 수요를 가진 세 개의 터미널. 각 터미널은 집으로 가는 두 경로가 있습니다. 비싼 직통 경로, 또는 공유 척추를 경유하는 무료 우회 경로.

긴장은 구조적입니다. 저렴한 우회 경로들이 척추의 공간을 두고 경쟁하기 때문에, 너무 많은 터미널이 동시에 저렴한 경로를 쓰려 하면 척추의 한 도로가 넘칩니다. 그 지점까지 밀어붙이면, 유효한 분할 불가 라우팅에서는 오직 한 터미널만 저렴한 경로를 탈 수 있습니다. 나머지는 비싼 직통 경로를 강제로 타야 하고, 비용이 오른습니다. 분수 플로우는 자유롭게 분할할 수 있어 각 수요를 두 경로에 나눠 싣고 모든 용량 제한 아래로 미끄러지듯 지나갑니다. 이렇게 해서 분수 비용이 최저의 합법적 분할 불가 비용보다 낮아집니다. Rybin이 제시한 수치는 58과 60입니다.

여기서 한계를 솔직히 밝히겠습니다. 1차 자료에서 Rybin의 정확한 그래프, 즉 구체적 용량과 쌍대 충돌을 재현하지는 못했습니다. 그의 대화록은 매개변수 가족의 특정 지점을 설명하며, 널리 공유된 "7노드" 설명은 그 추상화이지, 제가 모서리마다 검증한 구성은 아닙니다. 그래서 제가 58을 말끔히 유도해 그의 것인 양 연출하지는 않겠습니다. 대신 제가 할 수 있는 것은 같은 메커니즘을 보여주는 자족적인 인스턴스를 건네는 일입니다. 완전 탐색으로 확인할 만큼 충분히 작아서, "분수가 모든 합법적 분할 불가보다 유리"가 실제로 어떻게 보이는지 직접 확인하실 수 있습니다. 

네 개의 프롬프트, 몇 시간

프롬프트 개수는 이 이야기에서 가장 덜 흥미로운 부분입니다. 바이럴된 부분이기도 하지만요.

Rybin이 공유한 대화 로그는 모델이 먼저 실패하고, 그것을 정확히 인정하는 모습을 보여줍니다. 첫 프롬프트는 구조화된 반례를 찾으라고 했습니다. 모델은 한 시간 가까이 작업하고도 빈손으로 돌아와, 자신이 가진 것을 유효한 반례로 제시하는 것은 거짓이라고 분명히 밝혔습니다.

계속하라는 지시에 다시 실행했고, 이번에도 아무것도 없다고 보고했습니다. 유망해 보이던 각 구성이 모든 경로를 열거하면 숨어 있던 추가 라우팅 옵션이 나타나 비용-혼잡 분리를 무너뜨린다고 설명했습니다. 세 번째로 더 깔끔한 전략을 요구하자 더 좁은 틀이 제시되었지만 여전히 완성된 결과는 나오지 않았습니다.

이건 "네 프롬프트에 끝"이 아닙니다. 모델이 벽에 부딪히며 그 사실을 말한 몇 시간이었습니다. 모델이 계속 맞닥뜨린 특정한 벽, 즉 추가 경로가 나타나 분리를 망치는 문제가 바로 최종 구성에서 방지된 것입니다. 각 터미널을 정확히 두 경로에 고정해 전체 라우팅 공간을 손으로 열거 가능한 여덟 가지로 만든 것이죠. 그 실패 모드를 기억해 두세요. 곧 직접 겪게 됩니다.

네 번째 프롬프트는 전해진 바에 따르면 "이제 그만 실패하고, 조건 없는 완전한 반례로 마무리해 주세요"에 가까웠고, 이때 작동하는 구성과 함께 증명 증명서, 열거 프로그램, 전체 LaTeX가 생성되었습니다. 인내가 중요했습니다. 앞선 거절 또한 의미 있었습니다. 정직한 자기 평가였으니까요.

직접 확인해 보세요

여기서 DataCamp의 보도는 일반 뉴스 글이 할 수 없는 일을 할 수 있습니다. 바로 검증을 직접 돌려보는 일입니다.

코드로 가기 전에 짧은 주의사항. 아래는 Rybin의 그래프가 아닙니다. 각 터미널이 진짜로 정확히 두 경로만 갖도록 만든, 산술이 닫히고 격차가 실제로 존재하는 정직한 개략 인스턴스입니다. 이런 반례의 형태와 이를 점검하는 기법을 보여줍니다. 이것만으로는 어떤 것도 반박하지 못하며, 실행 직후 그 이유를 설명하겠습니다.

설정: 세 터미널이 각각 10 단위를 배송하며, 가장 큰 수요 D는 10입니다. 각자 비싼 직통 경로(비용 30)와 무료의 저렴한 경로를 가집니다. 저렴한 경로는 모든 쌍이 자신만의 병목 도로에서 충돌하도록 배열됩니다. 도로 A는 터미널 1과 2가, 도로 B는 1과 3이, 도로 C는 2와 3이 공유합니다. 분수 플로우에서는 각 터미널이 수요의 2/5를 저렴하게, 3/5를 비싸게 보내 비용이 30 x 3/5 x 3 = 54가 됩니다. 각 도로는 분수로 4 + 4 = 8 단위를 실으며, 혼잡 예산은 그 적재량에 D를 더한 18입니다.

이제 분할 불가 라우팅이 어떻게 되는지 보세요. 두 터미널이 모두 저렴 경로를 타면 공유 도로에 10 + 10 = 20 단위가 쏟아져, 예산 18을 초과합니다. 따라서 많아야 한 터미널만 저렴 경로를 탈 수 있고, 나머지 둘은 각각 30을 냅니다. 합법적 분할 불가의 최소 비용: 60. 분수는 54. 라우팅은 여덟 가지이므로 전부 확인해 봅니다:

from itertools import product
	
# Three terminals, demand 10 each -> largest demand D = 10.
# Each has a cheap path (cost 0) and an expensive direct path (cost 30).
# Cheap paths pairwise share a PRIVATE bottleneck road, so every pair conflicts:
#   road A shared by {t1, t2},  road B by {t1, t3},  road C by {t2, t3}
# NOTE: this is a schematic instance to illustrate the check, not Rybin's graph.

demands = [10, 10, 10]
d_max = max(demands)          # congestion slack allowed on each road
cheap_frac = [2/5, 2/5, 2/5]  # expensive fraction is 3/5 each -> fractional cost 54
direct_cost = 30              # cost of one terminal's expensive path

# Which bottleneck roads each terminal's cheap path uses
uses = [
    {"A": True,  "B": True,  "C": False},  # t1: A, B
    {"A": True,  "B": False, "C": True},   # t2: A, C
    {"A": False, "B": True,  "C": True},   # t3: B, C
]

# The fractional flow saturates each road, so its load is that road's capacity
cap = {"A": 0.0, "B": 0.0, "C": 0.0}
for i in range(3):
    for road in cap:
        if uses[i][road]:
            cap[road] += cheap_frac[i] * demands[i]   # 8 units on each road

# Congestion rule: an unsplittable flow may exceed capacity by at most D
threshold = {road: cap[road] + d_max for road in cap}  # 18 on each road

fractional_cost = sum(direct_cost * (1 - cheap_frac[i]) for i in range(3))  # 54

print(f"Capacities (fractional load): {cap}")
print(f"Congestion budget per road  : {threshold}")
print(f"Fractional flow cost        : {fractional_cost}\n")
print(f"{'Route (0=cheap,1=exp)':22} {'Cost':>4} {'A':>3} {'B':>3} {'C':>3}  Valid")

valid_costs = []
for choices in product([0, 1], repeat=3):    # 0 = cheap, 1 = expensive
    cost = sum(direct_cost * c for c in choices)
    load = {"A": 0, "B": 0, "C": 0}
    for i, expensive in enumerate(choices):
        if expensive == 0:                    # this terminal takes its cheap path
            for road in load:
                if uses[i][road]:
                    load[road] += demands[i]
    ok = all(load[road] <= threshold[road] for road in load)
    tag = "OK" if ok else "overload"
    print(f"{str(choices):22} {cost:>4} {load['A']:>3} {load['B']:>3} {load['C']:>3}  {tag}")
    if ok:
        valid_costs.append(cost)

print(f"\nMin valid unsplittable cost: {min(valid_costs)}")
print(f"Gap: {min(valid_costs) - fractional_cost} (counterexample if > 0)")

실행하면 분수 비용 54, 합법적 분할 불가 최소 비용 60, 격차 6이 나옵니다. 과부하가 뜨는 세 줄은 세 쌍의 충돌을 뜻합니다. 살아남는 라우팅은 많아야 한 터미널만 저렴 경로를 택하는 경우뿐입니다.

그렇다면 추측은 끝난 걸까요? 아직입니다. 이 부분을 설명하기로 약속했죠. 여덟 줄의 열거가 진실을 말하려면, 각 터미널이 정말로 두 경로만 가지고 있어야 합니다. 이 그래프를 실제 도로와 노드로 구성하면, 조합에서 네 번째 저렴 경로가 나타나는 경향이 있습니다. 터미널이 예산 안에서 유지되는 세 번째 저렴한 귀로를 찾아 격차가 닫히는 겁니다. 그 추가 경로가 바로 모델이 처음 세 번 시도에서 보고한 실패입니다. 깔끔하고 대칭적인 장치가 파이썬 여덟 줄로 30년 된 추측을 깨뜨린다면 너무 좋겠지만, 그렇지 않습니다. 위 코드는 검사가 건전하고 목표 속성이 현실적임을 보여줍니다. 특정 그래프가 실제로 그 속성을 누수 없이 갖는지는 어려운 부분이며, 그래서 Rybin의 실제 인스턴스가 말끔한 삼각형이 아니라 매개변수 가족의 조율된 지점인 것입니다.

아직 미해결인 것들

정식 논문은 나오지 않았습니다. Rybin은 대화와 구성을 공유했지만, 추측을 공식적으로 닫을 수 있도록 하는 심사를 거치지 않았습니다.

공개된 정확한 그래프는 제가 찾기엔 1차 자료에서 독립적으로 재구성되지 않았습니다. 돌고 있는 수치는 그의 게시물과 공유된 대화록에서 나옵니다. 여러 연구자가 그의 산술을 확인해 일관적이라고 했고, 한 명은 그의 인스턴스가 동일한 노드 위의 무한한 3매개변수 가족 안에 놓인다고 보였습니다. 단발의 행운보다 풍부한 결과일 수 있다는 뜻이죠. 고무적이지만 어디까지나 비공식 커뮤니티 점검이지 심사 보고서는 아닙니다. 58 대 60을 잘 뒷받침된 주장으로 대하되, 확정 사실로 보지는 마세요.

1999년의 혼잡 정리는 이와 무관합니다.

반복되는 패턴의 일부

이 이야기는 단발의 데이터 포인트가 아닙니다. 약 석 달 사이 AI 보조로 무너졌다고 보고된 세 번째 추측이며, 이 패턴은 곱씹을 만합니다.

7월 20일, Claude Fable 5는 수학자 Levent Alpöge가 야코비안 추측의 반례을 찾는 데 도움을 준 것으로 알려졌습니다. 87년 된 문제였습니다. 그 전 5월에는 OpenAI 모델이 80년 된 에르되시 단위-거리 추측을 반박한 것으로 전해졌습니다. 이 뉴스와 같은 주에 한 컬럼비아 박사과정 학생은 GPT-5.6을 구조화된 Codex 워크플로와 함께 사용해 5일 만에 6개의 미해결 에르되시 문제를 해결했습니다. 한 연구자가 말했듯 공통점은, 이런 시스템이 증명보다 반증에 더 능하다는 것입니다. 반례는 하나의 증인만 확인하면 되지만, 증명은 모든 경우를 덮어야 합니다. 그 비대칭성이 어떤 문제가 먼저 무너지는지를 좌우하는 듯합니다.

실질적인 교훈은 "AI가 수학을 푼다"가 아닙니다. 우리가 보는 것은 AI가 인내심 있는, 조합적으로 철저한 탐색 파트너로 작동하는 모습입니다. 매개변수 가족을 열거하고, 실패 모드를 시도 간 작업 기억에 붙잡아 두며, 구성이 닫히지 않을 때 사실대로 말할 수 있는 파트너 말이죠. 이는 구체적이고 유용한 역량입니다. 다음에 어디를 겨눌지 이해하고 싶다면, 얼마나 오래된 추측이냐가 아니라 하나의 검증 가능한 증인으로 무너질 수 있는지 여부를 물어보는 것이 맞습니다.