지수시간 가설이란 무엇인가
지수시간 가설(ETH)은 논리 문제의 난이도가 문제 크기에 따라 얼마나 빠르게 증가하는지를 기술하는 계산복잡도 이론의 핵심 가설이다. 여러 조건을 동시에 만족하는 참·거짓 값의 조합을 찾는 충족 가능성 문제(SAT)를 예로 들면, 조건 수가 늘어날수록 탐색 시간이 기하급수적으로 커진다는 것이 요지다. UC샌디에이고의 Russell Impagliazzo, Ramamohan Paturi, 그리고 Francis Zane은 이 가설로부터 그래프 채색 문제, 네트워크 내 특정 집합 탐색 등 다양한 문제의 계산 한계를 도출한 바 있다.
OpenAI의 주장과 검증 구조
OpenAI는 AI 시스템이 생성한 ETH 반증 증명을 공개하면서, 수학 정형 검증 소프트웨어 Lean을 통해 각 논리 단계의 타당성을 기계적으로 점검했다고 밝혔다. 외부 검증은 가설 수립에 직접 참여한 Impagliazzo와 Paturi, 그리고 MIT의 Ryan Williams가 이끄는 협력팀이 맡는다. Lean은 제공된 정의와 가정에 기반해 각 추론 단계를 형식적으로 확인하므로 AI가 생성한 그럴듯한 설명과는 구별된다. 다만 소프트웨어는 입력된 명제만을 검증하기 때문에, 해당 명제가 원래 계산 문제를 정확히 포착하는지는 연구자들이 별도로 판단해야 한다. 외부 협력팀은 증명의 논리 구조를 해설하고 다른 연구자들이 참고할 수 있는 형태로 정리하는 역할도 담당한다.
양자컴퓨팅 우위 논거에 미치는 파급
일부 양자컴퓨터 우위 주장은 고전 컴퓨터가 특정 계산을 얼마나 효율적으로 수행할 수 있는지에 대한 가정, 즉 강화 지수시간 가설(SETH) 같은 관련 가정에 근거한다. 양자 회로 진폭의 고전적 시뮬레이션 한계를 다룬 일부 연구에서도 이러한 가정이 보조 전제로 활용된 사례가 있다. 만약 ETH 반증이 검증된다면, 이 가정에 의존하는 결론은 독립적인 수학적 근거를 새로 확보해야 한다. 반면 가정과 무관한 실증적 결과나 독립적 수학 결과는 영향을 받지 않는다. 이번 발표 자체가 실질적인 양자 우위의 변화를 확정하지는 않는다.
반증이 의미하는 것과 의미하지 않는 것
ETH를 반증한다고 해서 관련 문제들이 곧바로 실용적으로 풀리게 되는 것은 아니다. 준지수(subexponential) 알고리즘이 이론적으로 존재하더라도, 변수 1,600개 짜리 문제에서 약 1조 번의 연산이 필요한 경우처럼 실용성과는 거리가 있을 수 있다. 이론적 개선이 소규모 문제에서는 오히려 오버헤드로 상쇄되는 경우도 있다. ETH 반증이 P 대 NP 문제를 해결하는 것도 아니며, 준지수 시간은 P 대 NP에서 쟁점인 다항 시간과 여전히 큰 차이가 있다. 수학적 결과가 현실 컴퓨터에서 실제로 빠른 알고리즘으로 이어지는지는 별도의 후속 연구가 필요하다.
별도의 양자장이론 관련 주장
OpenAI는 양자색역학(QCD)을 비롯한 양자장이론에 대한 수학적 존재 증명을 AI로 생성했다고도 발표했다. 노벨 물리학상 수상자인 David Gross가 이끄는 별도 협력팀이 이를 검토할 예정이며, 관련 AI 생성 자료는 검토 완료 전까지 공개되지 않는다. 이번 주장 가운데 순수 양-밀스(Yang-Mills) 이론의 존재 증명은 클레이수학연구소 밀레니엄 문제의 일부 요건에 해당한다. 그러나 질량 간격(mass gap) 증명을 포함한 전체 요건을 충족한 것은 아니므로, 밀레니엄 문제의 완전한 해결로 보기 어렵다.
전문은 원문에서 읽으세요
이 글은 Claude 가 원문의 사실을 재구성한 편집 요약입니다. 원제: OpenAI Computing Claim Faces Review, Raising Questions About Quantum Advantage
