AI와 AGI 시대를 살아가는 우리를 위한 테크 블로그. 인공지능 뉴스와 기술 동향을 알기 쉽게 전합니다.
수백 편 논문의 전제가 흔들린다 — AI의 지수 시간 가설 반박 주장
수학이나 컴퓨터과학 논문에는 종종 "이 가정이 참이라면"이라는 단서가 붙는다. 그 단서 위에 수백 편의 결과가 쌓였다. 그런데 그 단서 자체가 틀렸을 수 있다는 주장이 나왔다. 그것도 사람이 아니라 AI가 낸 증명으로.
주인공은 지수 시간 가설, ETH다. 3-SAT이라는 문제를 얼마나 빨리 풀 수 있는지에 대한 가설이다. 3-SAT은 참·거짓 조건들의 집합을 모두 만족시킬 수 있는지를 묻는 문제다. 변수가 하나 늘어날 때마다 경우의 수는 두 배가 된다. ETH는 이 문제를 지수 시간보다 의미 있게 빠르게 풀 수는 없다고 말한다. P 대 NP 문제와도 깊이 연결된, 오래 믿어온 규칙이다.
연구자들은 이 가설을 발판으로 삼았다. 그래프 이론, 계산 생물학, 데이터베이스, 계산 기하학 등에서 "ETH가 참이라면 이 작업은 이보다 빨라질 수 없다"는 조건부 한계 결과를 수백 편이나 도출했다. 전제가 튼튼하다고 믿었기 때문이다.
ETH는 수십 년 전 임팔리아초·파투리·제인이 제안한 뒤, 컴퓨터과학의 표준 도구로 자리 잡았다. P 대 NP 문제 자체는 여전히 열려 있지만, ETH는 그보다 강한 가정을 이용해 구체적인 문제마다 한계를 그을 수 있게 해줬다. 그래서 ETH는 '믿어지는 가설'이자 '일하는 가설'이었다. 증명이 아니라 전제로 쓰이면서도, 아무도 그 전제를 직접 흔들지 못했던 것이다.
2026년 10월 26일, OpenAI가 발표했다. 자사 내부 모델이 세 가지 결과를 만들었다고 했다. 수학의 국소 평활 추측 증명, 컴퓨터과학의 ETH 반박, 물리학의 양자색역학과 표준모형 완성에 대한 존재 증명이다. 오늘 이야기는 그중 두 번째, ETH 반박이다.
시간 순서가 흥미롭다. 모델이 ETH 반박의 자연어 원고를 만든 건 10월 16일, Lean이라는 증명 보조 도구로 형식화한 건 다음 날인 10월 17일이다. 자연어 원고와 Lean 증명은 모두 GitHub에 공개돼 있다. Lean 문서에 따르면, 형식화된 증명은 고정된 절 길이에 대해 표준 인코딩된 식의 만족 할당 개수를 준지수 시간과 다항식 공간으로 정확히 센다는 내용이다. ETH가 불가능하다고 말한 바로 그 영역이다.
여기서 조심해야 할 말이 있다. Lean이 확인한 것은 형식화된 명제가 논리적으로 닫혀 있다는 것이지, 그 결과가 학계에 받아들여졌다는 뜻은 아니다. OpenAI 스스로도 이번 원고를 "날것의 연구 데이터"라고 불렀다. 완성된 과학이 아니라, 이제부터 이해로 바꿔야 할 재료라는 뜻이다.
'준지수 시간'이라는 말도 풀어보자. 다항식 시간보다는 느리지만, 지수 시간보다는 빠른 영역이다. ETH는 3-SAT을 지수 시간보다 의미 있게 빠르게 풀 수 없다고 말했는데, 이번 증명은 그 경계 안쪽으로 들어가는 알고리즘을 제시했다는 주장이다. 다만 Lean이 검증한 것은 형식화된 문장 자체다. 그 문장이 원래 가설이 묻던 것과 정확히 같은 것인지는 사람이 따로 확인해야 한다. 기계가 단계를 검사하는 것과, 증명이 무엇을 뜻하는지 해석하는 것은 다른 일이다.
3-SAT이 왜 이렇게 중요한지도 짚어보자. 참·거짓 변수들로 조건을 만드는 문제는 시간표 짜기, 회로 설계, 일정 조정 같은 실제 문제의 뼈대와 닮았다. 변수가 30개면 경우의 수는 10억을 넘는다. 그래서 "이보다 빠른 방법은 없다"는 한계 결과는 실용적으로도 의미가 컸다. ETH를 전제로 한 연구들은 데이터베이스 질의 최적화나 그래프 문제에서 "여기까지가 한계"라는 선을 그어 왔다. 그 선이 흔들리면, 한계라고 믿었던 지점들을 다시 그어야 한다.
그래서 검증 방식이 눈길을 끈다. 검증을 주도하는 사람은 놀랍게도 ETH를 처음 제안한 사람들이다. 러셀 임팔리아초와 라모한 파투리(UC 샌디에이고), 그리고 MIT의 라이언 윌리엄스다. 이들은 OpenAI에 모든 원자료 공개와 학회 자금 지원을 요청했고, OpenAI가 동의했다. 제안자가 직접 자기 가설의 반박을 검증하는 셈이다.
이들의 참여가 곧 인증은 아니다. OpenAI 발표의 원칙에도 나와 있다. 참여는 자발적이고 무보수이며, 결론은 각자 것이다. 누구도 OpenAI를 대신해 말하지 않고, OpenAI도 이들을 대신해 말하지 않는다. 검증 그룹의 결론이 나올 때까지 반박은 '주장'으로 남는다.
만약 반박이 맞다고 확인되면 무엇이 바뀌나. 먼저 수백 편 논문이 하루아침에 틀리는 것은 아니다. 그 논문들은 "ETH가 참이라면"이라는 조건 아래에서 맞다. 바뀌는 것은 조건이다. 전제가 사라지면 그 위에 세워진 한계 결과들은 다시 검토해야 한다. 어떤 작업이 실제로 얼마나 빨라질 수 있는지는 다시 묻는 문제가 된다.
실용적인 기대도 조절해야 한다. OpenAI도 밝혔다. 이론적 진전이 실제 알고리즘 개선으로 이어지려면 상당한 추가 연구가 필요하다고 했다. 컴퓨터가 내일 갑자기 빨라지는 이야기가 아니다. SAT 풀이기가 빨라지려면 이론을 알고리즘으로 바꾸는 긴 과정이 필요하다.
함께 발표된 나머지 두 결과도 짚어두자. 수학에서는 1991년 소게의 국소 평활 추측을 모든 차원에서 증명했다는 주장이다. 파동이 극단적으로 모이는 현상에 대한 추측으로, 가케야 추측과 슈타인 제한 추측도 함께 푼다고 한다. 2차원은 2019년에, 3차원 가케야는 2025년에 풀렸던 문제다.
물리학 결과는 더 조심스럽다. 4차원 양자색역학과 표준모형 완성에 대한 존재 증명, 그 부분 문제로 순수 양-밀스 이론의 존재 증명을 포함한다. 다만 AI가 만든 자료는 아직 공개되지 않았다. 노벨상 수상자 데이비드 그로스가 이끄는 그룹이 자료를 직접 정리해 논문으로 쓰겠다고 해서, 공개를 미뤘다. 양-밀스 존재만으로 클레이 밀레니엄 문제 전체가 풀린 것도 아니다. 질량 간극 증명은 별개다.
이 발표가 던지는 더 큰 질문은 따로 있다. AI가 만든 증명을 학계가 어떻게 받아들일 것인가다. 증명의 길이가 길고, 사람이 직접 따라가기 어려울 때 검증은 누가, 어떻게 하는가. OpenAI의 이번 방식, 외부 전문가를 '셰퍼드'로 세워 공개 여부까지 맡기는 실험은 그 질문에 대한 하나의 답이다.
검증을 주도하는 사람이 원제안자라는 점은 의미가 크다. 자기 가설이 틀렸을 수 있다는 주장을 남에게 미루지 않고 직접 검증대에 올리는 모습이기 때문이다. 과학에서 전제가 흔들리는 순간은 드물지 않다. 다만 이번에는 그 흔들림을 만든 주체가 AI이고, 증명의 형태가 사람이 읽기보다 기계가 검사하기에 적합한 파일이라는 점이 새롭다. OpenAI는 이달 초 수학 결과 공개 때도 같은 방식으로 원고와 Lean 증명을 함께 내놓은 바 있다. 이번 발표는 그 방식을 세 분야로 넓힌 것이다.
앞으로 지켜볼 대목은 세 가지다. 첫째, 검증 그룹이 형식화된 명제와 원래 가설 사이의 간격에 대해 어떤 판단을 내리는지. 둘째, 사람이 읽을 수 있는 설명이 나오는지. 길고 기계적인 증명이 이해 가능한 이야기로 바뀌어야 학계 전체가 받아들일 수 있다. 셋째, 반박이 맞다고 확인될 경우, 조건부 한계 결과들을 다시 세우는 작업이 어디서부터 시작되는지다. 이 세 가지가 채워질 때까지, 이 소식은 '주장'이라는 꼬리표를 달고 있어야 한다. 이들의 중간 결론이 나올 때마다 이야기는 달라질 수 있다. 그래서 이 글도 결론을 내리지 않는다. 전제가 흔들린다는 소식, 그리고 그 흔들림을 확인하는 과정이 지금 진행 중이라는 사실까지가 오늘 전할 수 있는 전부다.
검토 과정 자체도 눈여겨볼 만하다. 원자료가 GitHub에 공개돼 있어, 검증 그룹뿐 아니라 전 세계 연구자가 같은 증명을 들여다볼 수 있다. OpenAI는 이 작업의 의미를 논의하는 학회 자금도 지원하기로 했다. 예전 같으면 논문 한 편이 심사위원 몇 명의 손을 거쳤겠지만, 이번에는 증명 파일 자체가 공개 검토의 대상이다. AI 시대의 검증이 어떤 모습이어야 하는지를 보여주는 사례가 될 수 있다.
오래 믿어온 규칙이 흔들릴 때, 과학은 무너지는 것이 아니라 다시 묻는다. 이 작업은 정말로 얼마나 빨라질 수 있는가. 그 질문이 다시 열렸다는 것, 그 자체가 이번 발표의 의미다. 그리고 그 답을 확인하는 과정 자체가, AI 시대 과학의 새로운 검증 방식이 될 수 있다.
출처: OpenAI 공식 발표 'Working with academic communities to build scientific understanding'(https://openai.com/index/building-scientific-understanding-with-academic-communities/), GitHub openai/math Lean 문서(https://github.com/openai/math/blob/main/lean/docs/378.md)
