GPT-5.6와 Dinitz-Garg-Goemans 추측

2026년 7월 22일, Dmitry Rybin이 X에 올린 한 주장에 일부 사람들은 커피를 내려놓았습니다. GPT-5.6 Pro가 약 30년간 조합최적화 분야에서 열려 있던 Dinitz-Garg-Goemans 추측의 반례를 만들어냈다는 것입니다. 증거 개념은 작은 그래프 하나였습니다. 분할 가능(fractional) 흐름 비용은 58, 분할 불가(unsplittable) 흐름 비용은 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이 겨냥한 부분은 나머지 절반입니다. 왜 그 구분이 크게 중요한지 이해하려면, 정확히 짚고 넘어가야 합니다.

정리(Theorem)와 추측(Conjecture)의 차이

많은 글이 이 구분을 흐리니, 여기서 한 번 정확히 짚고 이후 내내 이 구분에 의존하겠습니다.

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

Goemans가 별도로 추측한 것은 더 강한, 비용까지 고려한 버전입니다. 같은 변환이 혼잡을 억제하는 동시에 총비용도 낮게 유지할 수 있다는 것. 혼잡과 비용을 모두 묶어 제한하는 하나의 라우팅. 혼잡만을 다루는 정리는 안전합니다. 비용+혼잡을 함께 묶는 추측이 Rybin이 무너뜨렸다고 말하는 부분입니다. 이 글에서 한 문장만 가져가신다면 이것으로 해 주세요. 많은 흥분한 보도들이 둘을 조용히 바꿔치기하는데, 그 차이야말로 30년이 걸린 수학적 간극의 전부입니다.

GPT-5.6이 실제로 만든 것

Rybin의 예시는 한 문단으로 설명할 만큼 작습니다. 하나의 소스, 공유된 "척추"를 이루는 몇 개의 중간 노드, 그리고 각자 수요를 지닌 세 개의 터미널. 각 터미널은 귀로가 두 개씩 있습니다. 비싼 직통 경로, 혹은 공유 척추를 경유한 무료 우회 경로.

긴장은 구조적입니다. 값싼 우회 경로들이 척추 위의 공간을 두고 경쟁하므로, 너무 많은 터미널이 동시에 저렴한 경로를 선택하려 하면 척추의 도로가 넘칩니다. 그 지점까지 밀리면 어떤 유효한 분할 불가 라우팅에서도 오직 한 터미널만 값싼 경로를 탈 수 있게 됩니다. 나머지는 비싼 직통 경로로 밀려나고 비용은 올라갑니다. 분할 가능한 흐름은 자유롭게 나눌 수 있으므로 각 수요를 두 경로에 분산시켜 모든 수용량 제한을 동시에 비껴갑니다. 이렇게 해서 합법적인 분할 불가 최소 비용보다 낮은 분수 비용이 나옵니다. Rybin의 수치는 58과 60입니다.

여기서 한계를 솔직히 밝히겠습니다. 1차 출처만으로 Rybin의 정확한 그래프, 즉 구체적 수용량과 쌍별 충돌 관계를 재현하지는 못했습니다. 그의 대화록은 매개변수 계열의 특정 지점을 설명하고 있으며, 널리 공유된 "일곱 노드" 설명은 그 추상화이지 제가 모서리 하나하나 검증한 구성은 아닙니다. 그래서 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가 Jacobian 추측의 반례을 찾는 데 도움을 준 것으로 전해졌습니다. 87년 된 문제였습니다. 그 전 5월에는 OpenAI 모델이 80년 된 에르되시 단위 거리 추측을 반증했다고 알려졌습니다. 이번 뉴스와 같은 주에, 콜롬비아대 박사 과정 학생이 구조화된 Codex 워크플로와 GPT-5.6을 사용해 5일 만에 여섯 개의 열린 에르되시 문제를 해결했습니다. 한 연구자가 말했듯, 이 시스템들은 증명보다 반증에 더 능합니다. 반례는 확인 가능한 단 하나의 증인이면 되지만, 증명은 모든 경우를 덮어야 합니다. 그 비대칭이 어떤 문제가 먼저 무너지는지를 좌우하는 듯합니다.

실질적인 교훈은 "AI가 수학을 푼다"가 아닙니다. 우리가 보는 것은 AI가 인내심 있게 조합적으로 철저히 탐색하는 파트너로 일하는 모습입니다. 매개변수 계열을 열거하고, 실패 모드를 시도 간 작업 기억에 유지하며, 구성이 닫히지 않으면 사실대로 말하는 파트너 말이죠. 이는 구체적이고 유용한 역량입니다. 다음에 어디에서 효과를 낼지 이해하고 싶다면, 가장 오래된 추측이 무엇인지가 아니라, 단 하나의 검증 가능한 증인으로 깨질 수 있는 추측이 무엇인지를 물어야 합니다.