OpenAI가 연구자들을 오랫동안 괴롭혀 온 세 개의 획기적인 수학 문제에 대한 솔루션을 공개했습니다. 그중 하나는 지수 시간 가설(ETH)에 대한 놀라운 반박이었는데, 이는 계산 과학에서 오랫동안 유지되어 온 가설로, 무엇이 계산하기 어려운지를 우리가 이해하는 방식에 큰 역할을 합니다.
해당 프런티어 연구소의 이전 증명 드롭과 마찬가지로, 과학계는 흥분과 경악이 뒤섞인 반응을 보였다. Anthropic의 수학자 Levent Alpöge 제안됨 OpenAI가 기존 연구 성과를 기반으로 자사 솔루션을 만들었다는 내용이었고, 몇 시간 후 Anthropic은 이어서 공개됨 ETH에 대한 그 자체의 반박입니다.
그러나 OpenAI의 프로세스는 진화하고 있습니다. 이번에 이 연구소는 릴리스를 구성했다 세 분야 각각마다 다르게 진행되었습니다: 수학자들은 작업 결과를 GitHub에 공개했습니다; 컴퓨터 과학자들은 실무 그룹을 구성하여 증명을 공개적으로 공유할 것과 이를 논의할 컨퍼런스를 OpenAI가 지원해 줄 것을 요청했습니다; 물리학자들은 그들의 결과가 어떻게 공개될지 결정할 실무 그룹을 구성했습니다.
MIT 교수 라이언 윌리엄스(Ryan Williams)는 이번 새로운 발견에 대한 컴퓨터 과학 분야의 대응을 조직하고 있는 컴퓨터 과학자입니다. 계산 복잡도 문제를 연구하는 윌리엄스는 과거 OpenAI의 접근 방식을 비판한 바 있습니다. 호출 지난 10월 초 공개한 증명 자료 묶음을 두고 “수학자들에 대한 DDOS 공격”이라고 불렀다.
그러나 그는 이 분야에 중요한 아이디어를 잘 이끌어가는 데 도움을 주기 위해 프론티어 연구소들과 협력하기로 동의했다고 TechCrunch에 말했다. 이 연구소는 1999년 ETH를 처음 발표한 UC 샌디에이고 컴퓨터 과학자들인 Russell Impagliazzo와 Ramamohan Paturi와 함께 그가 이 해법을 해석하도록 돕기를 요청했다.
그들의 첫 번째 단계는 공개하는 것이었다 공개 서한 이러한 문제에 관심 있는 과학자들의 피드백과 AI의 연구 기여에 관한 규범 논의를 촉구하고 있습니다.
“OpenAI의 증명 중 일부는, 어쩌면 루틴하다고 말할 수 있지만, 그렇다면 두어세 개의 낯설어 보이는 부분이 있는데, 바로 제가 본 바로 그 부분들이 저로 하여금 ‘와, 이것은 온 커뮤니티가 함께 풀어야 할 과제’라고 생각하게 만든 부분입니다”라고 Williams가 TechCrunch에 말했습니다.
P 대 NP 문제에 대해 알고 계신가요?
ETH는 수십 년 동안 컴퓨터 과학과 여러 다른 분야를 활발하게 움직여온 P 대 NP로 알려진 더 넓은 문제 부류의 일부입니다. 단순화하자면, 연구자들은 해답을 쉽게 검증할 수 있는 (NP) 어떤 문제든 쉽게 풀 수 있는(P)지를 이해하려 하고 있습니다.
간단한 예는 스도쿠 게임입니다: 퍼즐의 해답이 한 번 놓이면 빠르게 검증할 수 있지만, 해답을 찾는 것은 시간이 오래 걸립니다. 이러한 역학은 다양한 중요한 문제들에 걸쳐 성립하며, 그 통찰은 암호 시스템의 기반이 됩니다: 인코딩된 메시지의 키가 있으면 그것을 드러낼 수 있지만, 실제로 효과적인 암호를 깨는 데는 유용하기에는 너무 오랜 시간이 걸립니다.
그러나 과학자들은 그것이 항상 참인지 아직 증명하지 못했습니다. “P = NP는 스도쿠 해답이 존재할 때 검증할 수 있을 뿐만 아니라 그것들을 그냥 생성할 수도 있다고 말하는 것입니다”라고 Williams가 말했습니다. “P = NP는 빠르게 검증할 수 있는 모든 단일 문제에 대해 이것이 참이라고 주장합니다 — 빠르게 검증할 수 있다면 빠르게 풀 수 있다는 것입니다. 그러니 이것은 너무 좋아서 사실 같지 않아 보입니다.”
그렇기 때문에 대부분의 과학자들은 P ≠ NP라고 가정합니다. ETH는 그에 대한 근거를 제공했습니다. 본질적으로, 특정 부류의 까다로운 논리 퍼즐에서 변수 수가 증가함에 따라 가장 빠른 컴퓨터 알고리즘조차 해답을 찾는 데 지수적으로 더 많은 시간이 필요하다고 말합니다.
OpenAI와 Anthropic의 주장은 그들의 모델이 그러한 퍼즐을 “준지수” 시간에, 즉 이전에 가능하다고 여겨졌던 속도보다 빠르게 푸는 알고리즘을 만들어냈다는 것입니다. 만약 사실이라면, 그들은 ETH(원문에서는 EFT로 표기)가 거짓임을 증명했을 수도 있습니다 — 과학 용어로 반박한 것입니다 — 그리고 일반적으로 P = NP를 수행하는 알고리즘의 길을 열었을 수도 있습니다.
“모든 컴퓨터 과학자는 아마도 P = NP의 그럴듯함에 조금 더 무게를 두어야 하겠지만, 그 무게는 사람마다 다를 수 있습니다”라고 Williams가 말했습니다. “저는 이것이 사실 … (어려운 NP 문제가) 얼마나 다루기 쉬운가에 대해 우리가 가지고 있다고 생각했던 많은 직관들에 의문을 제기한다고 생각합니다. 저는 또한 이것이 아마도 최종 답이 아니라고 생각합니다. OpenAI의 알고리즘이 얻을 수 있는 최선의 알고리즘일 수는 없다고 생각합니다.”
컴퓨터 과학자들에게 남은 과제
ETH의 견고함으로 인해 지난 10년간 많은 과학 논문에 포함되었으며, AI 연구소들이 그것을 반증했다는 주장이 받아들여진다면 이 논문들은 다시 살펴봐야 할 것이라고 Williams가 말했습니다.
“이것이 내가 이 주제에 관한 컨퍼런스를 지원하도록 OpenAI에 요청하거나 압박했던 부분적인 이유입니다 — 이것은 많은 연구자들의 연구에 영향을 미칠 것이고, 우리는 알고리즘을 이해하는 것 외에 다음에 무슨 일이 일어날지 파악해야 합니다. 우리는 이전에 가졌던 것과 비교하여 기초가 어떻게 바뀌어야 하는지 이해해야 합니다”라고 그는 말했습니다.
과학적 우려 이전에 사이버 보안 문제가 있습니다. Williams는 향상된 알고리즘이 특정 키 크기에 의존하는 암호화 시스템이 깨진 것으로 간주될 수 있음을 의미한다고 말했습니다. 그래서 그가 OpenAI 과학 책임자 Dan Roberts에게 던진 첫 번째 질문 중 하나는 “그들이 이것이 암호화 시스템에 영향을 미치는지 확인했는지 … 지금 불안전한 것이 있는가?”였으며, “다행히 그들은 확인했고, 이것이 … 어떤 깨짐도 의미하지 않는다는 데 상당히 확신하고 있었습니다.”
과학적 발견이라는 이 새로운 AI 패러다임은 아직 진행 중인 작업이지만, Williams는 특히 차세대 과학자 양성에 관한 실제 우려에도 불구하고 낙관적이라고 말합니다. 고급 수학을 다루는 컴퓨터 과학자라는 점이 순수 수학자들보다 그에게는 적응을 좀 더 쉽게 만들어주었을지도 모릅니다.
그럼에도 그는 AI가 “사람들이 자신이 하는 연구의 종류에 대해 좀 더 야심을 갖도록 하고, 자신이 하던 일들이 이제 AI에게는 쉽게 얻을 수 있는 저세상 열매라면, 내가 탐구하고 싶은 과학적 질문의 수준을 어떻게 높일 수 있을까를 더 깊이 생각하도록 만들고 있다”고 말합니다.