요약
OpenAI가 3-SAT를 지수 시간보다 빠르게 푸는 알고리즘을 내놓으며 지수 시간 가설을 반박했다고 주장합니다.
OpenAI가 수학·컴퓨터과학·물리학 발견 세 건을 발표하며 함께 공개한 67쪽짜리 논문입니다. 저자는 OpenAI로만 적혀 있습니다. 지수 시간 가설(ETH)은 3-SAT(논리식을 참으로 만드는 값이 있는지 묻는 문제)를 풀려면 최악의 경우 변수 수에 지수적인 시간이 든다는 추측입니다.
왜 중요한가
- 결과가 맞다면 ETH와 SETH(강한 지수 시간 가설)를 전제로 한 편집 거리 등 여러 문제의 속도 하한 증명이 근거를 잃습니다.
- 다만 이 속도는 일반적인 문제 변환으로는 옮겨지지 않아, 모든 NP 문제가 빨라진다는 뜻은 아니라고 논문이 밝혔습니다.
핵심 내용
- 변수 n개짜리 k-CNF(절마다 변수가 k개 이하인 논리식)의 해 개수를 약 2^(n/√log n) 시간에 정확히 세는 알고리즘을 제시했습니다.
- 이 알고리즘은 무작위성을 쓰지 않고, 메모리도 입력 크기의 다항식 수준만 씁니다.
- 지금까지 3-SAT 최고 기록은 무작위 알고리즘이 약 1.307^n, 결정론적 알고리즘이 약 1.328^n이었습니다.
- 절의 입력을 낮은 차수 다항식으로 바꿔 변수 묶음을 따로 합산하고, 보간(여러 점의 값으로 다항식을 되살리는 계산)으로 해 개수를 복원합니다.
- 입력 몇 개만 보는 함수(골드라이히의 일방향 함수 후보)도 역산할 수 있지만, 다항 시간 공격까지 되는 것은 아니라고 했습니다.
HN 반응
- 일부 이용자는 P≠NP 문제와는 직접 관계가 없다면서도, 생각지 못한 빠른 알고리즘이 더 있을 수 있다는 도널드 커누스식 직관이 힘을 얻을 수 있다고 봤습니다.
- 암호 영향을 두고는 라이언 윌리엄스가 OpenAI에 확인해 기존 암호는 안전하다고 했다는 소개와, AI 연구소가 암호 성과만 숨긴다는 의심이 맞섰습니다.
P-NP 문제와 당장 직접 관련은 없지만, 흥미로운 점이 있어 짚어 둡니다.
도널드 크누스 같은 초기 전산학 연구자들은 누군가 어떤 문제에 대해 놀랍도록 빠른 알고리즘을 심심치 않게 내놓던 시절에 이 분야에 들어왔고, 대부분의 문제에는 예상보다 빠른 알고리즘이 있을 것이라고 직관적으로 생각했습니다.
쉬운 알고리즘이 다 발견되고 카프가 NP-완전성을 정의한(예컨대 가리와 존슨의 책이 나온) 뒤의 세대는 난해함을 증명하는 쪽으로 전문화되었고, 복잡도 부류의 “동물원”을 이루는 복잡도 이론도 분리와 하한 증명 중심으로 바뀌었습니다. 예를 들어 유클리드 TSP에 대한 아로라의 PTAS가 “하한을 증명하려다 실패한 시도”라고 불리는 것을 본 적이 있습니다. 그러니 한 세대 전체 연구자들의 직관은 대체로, 깔끔한 분리 결과(증명은 못 하더라도)가 존재하는 우아한 우주 쪽을 향해 있었던 셈입니다.
그래서 전산학자 설문조사에서도 대다수가 P≠NP를 믿는 것으로 나왔고, P=NP일 수도 있다고 말하는 크누스 같은 사람은 늘 좀 별난 소수파로 보였습니다. 그의 논거는 단순했습니다. 우리가 아직 탐색하지 않은 다항 시간 알고리즘이 너무나 많으니, 그중 지수가 큰 어떤 알고리즘이 NP-완전 문제를 풀 수도 있다는 것입니다. (그런 알고리즘을 찾는 데 수많은 연구자가 실패했다는 반박에는, 수많은 연구자가 P≠NP를 증명하는 데도 실패했다고 답하곤 했습니다.) 예를 들어 2017년에 스콧 애런슨이 서베이( https://www.scottaaronson.com/papers/pnp.pdf = https://www.scottaaronson.com/papers/pnp-kindle.pdf )를 썼을 때 이렇게 적었습니다.
그러니 (P≠NP에 대한 직관이 바뀔 거라고 보지는 않고, 아마 그 직관이 여전히 맞겠지만… 저는 관심 많은 아마추어일 뿐입니다) 우리가 아직 생각하지 못한 영리한 알고리즘이 존재할지도 모른다는 생각 쪽으로 추가 약간은 되돌아갈 수도 있겠습니다.
최악의 경우는 지수적으로 어렵지만 평균적인 경우는 훨씬 빠른 어려운 문제들이 있습니다. 선형 계획법과 외판원 문제가 그렇습니다. 더 빠른 접근법은 “확률적 해법”으로 여겨집니다.
암호학에서 지수적으로 어렵다고 믿는 문제들은 대부분 소인수분해처럼 지수 하한이 증명되어 있지 않습니다. 돌파구가 나와서 그런 문제들이 쉬워질 위험이 어느 정도 있습니다. 확률적 해법만으로도 많은 암호 체계를 깨기에 충분할 수 있습니다.
전 세계 암호 해독 기관 사람들이 오늘 밤 이번 결과가 미칠 영향과 위험을 파악하느라 밤을 새우고 있을 것 같습니다.
확률적 알고리즘을 언급하시다니 공교롭네요. 제가 잘못 안 게 아니라면, 오픈AI 결과 중 하나가 확률적 방법 대부분(특히 로그 크기의 공간을 쓰는 것들)-4은 시간과 공간 면에서 똑같이 효율적인 비확률적 버전이 있다는 거예요(L = RL = BPL).
그건 결코 대부분이 아니고, 실용적으로 쓸모 있는 것들 대부분도 아닙니다. 인접 리스트를 입력으로 받는 방향 그래프 도달 가능성 문제는 NL-난해입니다.
선형 계획법에는 내부점 방법이 있고, 이건 최악의 경우도 다항 시간입니다.
게다가 확률적이지도 않으니, 선형 계획법은 그다지 좋은 예가 아니에요.
맥락상 Animats는 NP-완전 문제인 정수 선형 계획법을 말한 것 같습니다.
그리고 내부점 방법은 지수 시간 알고리즘(심플렉스)한테 툭하면 밀리잖아요 ㅋㅋ
참고로 라이언 윌리엄스는 이렇게 말했습니다( https://x.com/rrwilliams/status/2114891838377320784 ).
그러니 오픈AI에 대한 그의 신뢰를 믿는다면, 현재로서는 이번 결과가 암호 체계에 (당장 눈에 띄는) 영향을 주지 않습니다.
이번 결과로는 그렇지 않겠죠. 하지만 파고들면 어딘가에 닿을 수도 있는 새로운 문제 영역이 열린 겁니다.
요즘 PHP 생태계가 겁에 질려 있는 걸 보고, 예전에 금융 시스템에서 일해 본 입장에서 말씀드리면, 최첨단 모델이 우리 암호 체계의 바탕이 되는 수학 문제를 깨 버린다면 전 세계 은행업이 어떻게 될지 생각만 해도 끔찍합니다...
이상하게도 이들이 낸 폭넓은 결과가 수학의 모든 분야를 건드리는데 암호학과 닿는 것만 없어요. 정보기관들이 특정 발견의 발표를 거부할 수 있는 권한을 갖고 있다고 봐도 무리가 아니라고 생각합니다.
맨해튼 프로젝트도 핵과학자들이 일제히 논문을 내지 않기 시작해서 눈치챌 수 있었다고 하잖아요.
얼마 전에 주요 LLM 제공사가 거의 동시에 다운됐을 때, 그게 일종의 가상 “Room 641A” 같은 것 때문이었다는 댓글이 있지 않았나요?
세계의 수학 역량이 지금처럼 AI 연구소에 집중된 것의 문제 중 하나는, 그들이 효율적인 알고리즘으로 P=NP를 찾아낸다면 현대의 모든 공개키 기반 암호에 영향을 줄 수 있다는 점입니다. 그래서 그들이 그 결과를 공개할지(혹은 공개하도록 허락받을지)는 전혀 분명하지 않습니다.
이 주제를 다룬 저예산 SF 영화가 하나 있어요.
https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film)
https://www.youtube.com/watch?v=OgeyHkP6i3g (영화 전편)
이 주제를 다룬 책도 있어요.
https://www.goodreads.com/book/show/37986693-factor-man
설정이 정말 좋네요.
다른 수학 문제들은 한꺼번에 풀렸다고 하면서 암호학 쪽에서는 풀었다는 결과가 하나도 공개·발표되지 않았다는 사실이, “현대의 모든 공개키 기반 암호”가 위험에 처했을 수 있다는 강한 징후일 수 있습니다.
아니면 암호학에는 다른 수학 분야 대부분보다 더 많은 자원이 투입되어 와서, AI가 아직 우리의 진전을 따라잡지 못했다는 뜻일 수도 있고요.
나비에-스토크스 문제를 푸는 게 라운드 수를 줄인 AES에 대한 더 나은 공격보다 어렵다는 건 상당히 있을 법하지 않아 보입니다. 지수의 엡실론 정도 개선은 발표할 가치가 없다고 보는 걸 수도 있지만, 가진 결과를 일부러 숨기고 있을 가능성이 더 커 보입니다.
제가 잘못 이해한 걸 수도 있지만, 라운드 수를 줄인 AES에 대한 더 나은 공격은 LLM이 이미 해냈습니다. 앤트로픽이 해서 이미 발표했고, 라운드 수를 줄인 AES에 대해 기존 최고 기록을 “200~800배” 개선한 선택 평문 공격입니다. https://anthropic.com/document/aes_mobius_bridge.pdf
NSA 같은 기관이 암호 체계 설계에 관여했고, 백도어일 수 있는 구체적인 제안을 했다고 알려진 사례들은 전부 AI에게 찾아보라고 시키면 드러날 것이라는 추정은 합리적입니다. 어쩌면 일반에 공개되지 않은 모델들이 수행하는 더 폭넓은 방어 보안 연구의 일부로 간접적으로 드러날 수도 있겠죠. 알고리즘적 복잡성이든 정말 모호한 백도어든 정부가 암호 체계에 심어 놓은 게 있다면, 지금의 최전선 모델이 그것을 밝혀낼 가능성이 가장 높아 보입니다.
그게 아니면 그 문제들에 모델을 투입하지 않았을 수도 있어요. 나비에-스토크스 풀이에도 막대한 연산이 들어갔다는 걸 기억하세요. PR 효과를 못 얻는 문제에 그걸 쓰고 싶어 하지 않을 것 같아요.
“그럴 수 있다”는 건 맞지만, 정확하게 말하면 “일반 대중은 모른다”가 맞다고 봅니다. 가능성은 다음 중 아무거나일 수 있습니다.
열심히 시도했지만 약점을 찾지 못했다
한동안 시도하다가, LLM이 실마리조차 내놓지 못해서 포기했다
시도해서 뭔가 찾았고, 자기들끼리만 갖고 있다
저는 첫 번째가 있을 법하지 않은 일은 아니라고 봅니다. LLM 이전에도 NSA 같은 곳은 이 문제들을 정말 열심히 파고들었을 테고, 제 생각엔 실질적인 무언가를 찾았을 가능성은 낮습니다(찾았다면 다른 큰 나라의 상대 기관들도 찾았을 테고, 그중 일부는 그 지식을 써먹었을 테니까요).
저는 효율적인 알고리즘으로 P=NP를 증명하는 것보다 은하급 알고리즘(galactic algorithm)으로 증명하는 쪽이 훨씬 더 가능성이 높다고 생각합니다.
NP-완전 문제를 푸는 O(n^100) 알고리즘을 누군가 개발한다면 P=NP가 증명되겠지만, 암호에는 당장 아무 위협도 되지 않는다는 뜻이죠.
물론 위험을 높이기는 합니다. 은하급 알고리즘이 있다면 아직 발견되지 않은 효율적인 알고리즘이 존재할 확률이 올라가니까요. 하지만 은하급 알고리즘은 존재하는데 효율적인 알고리즘은 존재하지 않는 경우도 (인식론적으로는) 얼마든지 가능합니다.
반대로, P≠NP가 증명되었다고 해서 실용적인 n에 대해 충분히 빠른 알고리즘이 없다는 뜻도 아니고요.
그럴 수는 있지만 제게는 그쪽이 훨씬 더 특이하고 있을 법하지 않아 보여요. n이 천에서 백만 사이일 때는 무차별 대입의 자연스러운 비용 증가를 사실상 상쇄하다가, 그보다 커지면 그 속도 이점이 사라져야 하니까요.
글쎄요, NP-완전 문제에 대한 준다항 시간 알고리즘 – O(n^log(n)) – 이 발견된다면, 엄밀히는 P≠NP와 양립하겠지만 실용적으로는 꽤 큰 의미가 있을 수 있습니다.
문제 공간에 대한 제 이해가 불완전해서 그런 것일 수도 있습니다(말장난이 여러 개 섞인 점은 양해해 주세요). 그래도 저는 크누스가 정말 P=NP라고 말했는지 의심스럽습니다. P≠NP임을 분명히 보여 주는 수학적 예는 정말 많잖아요. 컴퓨팅 자체가 원래 어려운 문제를 반복적 방법으로 푸는 데서 출발했습니다. 최소제곱법, sin(), cos(), 외판원 문제 등 다 나열하기도 힘들 정도입니다. 모든 문제에 대해 P=NP라고 말하는 건 바보짓 같아 보입니다.
이 인터뷰에서 열일곱 번째 질문에 대한 그의 답변을 보세요.
https://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions