$\exists \mathbb{R} \subseteq \textsf{CH}$

컴퓨터 과학의 광활한 풍경 속에는 기계가 결정할 수 있는 한계에 대한 근본적인 질문이 존재한다. 어떤 문제들은 답을 일단 얻고 나면 확인하기 쉽지만, 다른 문제들은 처음부터 풀기 위해 불가능할 정도의 시간이 걸리는 것처럼 보인다. 이러한 양극단 사이에는 기하학과 숫자와 관련된 특히 까다로운 영역인 실수의 존재 이론(existential theory of the reals)이 자리 잡고 있다. 이 분야는 단순하지만 심오한 질문을 던진다. 다항 방정식과 부등식으로 작성된 일련의 규칙들이 주어졌을 때, 실제로 실수 해가 존재하는가? 만약 거리와 각도에 관한 복잡한 조건들을 만족하는 특정 지점을 지도에서 찾으려 한다고 상상해 보라. 어려움은 해가 되는 좌표가 믿기 힘들 정도로 크거나, 짧은 형태로 써 내려갈 수 없을 만큼 복잡한 숫자를 포함할 수 있다는 점에서 발생한다. 수십 년 동안 연구자들은 이 문제가 표준적인 퍼즐보다는 어렵지만, 가장 혼란스러운 계산적 악몽보다는 쉽다는 사실을 알고 있었으나, 난이도의 계층 구조 내에서 정확히 어디에 위치하는지는 밝혀내지 못해 고군분투해 왔다. 이 위치를 파악하는 것은 미술관 설계부터 복잡한 시스템의 안전성 검증에 이르기까지, 광범위한 기하학적 및 공학적 문제들에 대해 무엇이 계산적으로 실행 가능한지를 정의하기 때문에 매우 중요하다.

한 연구자가 첨단 인공지능 시스템과 협력하여 이 오래된 질문에 답하는 데 있어 중요한 진전을 이루었다. 그는 실수 해의 존재 여부를 결정하는 문제가 '카운팅 계층(counting hierarchy)'이라 불리는 구체적이고 잘 정의된 계산 난이도의 특정 층위에 속한다는 증명을 제시했다. 이는 이 문제가 이전까지 생각되었던 것보다 훨씬 낮은 수준의 난이도에 위치함을 의미하므로 중대한 성취이다. 연구자는 단순히 대략적인 추정치를 찾아낸 것이 아니라, 이 문제가 이 계층의 네 번째 단계(fourth tier)에 속한다는 것을 시사하는 수학적 논거를 구축했다. 이는 문제가 복잡하기는 하지만, 한때 우려했던 것처럼 다루기 힘든 수준은 아니며, 구조화된 방식으로 가능성을 세는 알고리в즘에 의해 제어될 수 있음을 의미한다.

이 발견으로 가는 길에는 영리한 관점의 전환이 있었다. 연구자는 기하학적 방정식의 정확한 해를 찾는 대신(그 해는 불가능할 정도로 클 수 있다), 시스템의 행동이 변하는 임계점(critical points)에 집중했다. 그는 원래의 문제를 유한한 대수적 구조로 변환하는 방법을 고안해 냈으며, 이를 통해 무한한 탐색 공간을 관리 가능한 후보 목록으로 효과적으로 바꾸어 놓았다. 이 후보들의 특성, 구체적으로는 그들이 어떻게 곱해지고 상호작용하는지를 분석함으로써, 해를 직접 써 내려가지 않고도 해의 존재 여부를 결정할 수 있었다. 그 방법의 핵심은 몇 가지 특정 부호(sign)를 확인하는 것만으로 군중 속에서 하나의 유효한 해를 분리해 내는 기술에 달려 있는데, 이는 마치 누군가의 전체 역사를 설명하는 대신 몇 가지 특정 특징을 확인하여 용의자를 좁혀가는 것과 같다.

이 작업의 가장 놀라운 측면 중 하나는 인간 연구자와 인공지능 사이의 협업이다. 인간 저자인 알렉스 메이버그(Alex Meiburg)는 증명들이 필수적인 논거를 생성해 낸 AI와의 일련의 대화를 통해 개발되었다고 언급한다. 인간 연구자는 증명이 올바르게 보이는 것에 대한 책임을 지지만, 이를 개발하는 데 있어 비사소한(nontrivial) 역할은 수행하지 않았다. 이 원고는 그러한 협업에 대한 공개 기록으로서, 더 넓은 과학계가 서로 다른 증명 기법들을 비교할 수 있도록 한다. 흥미롭게도, 이 작업이 완료된 직후 동일한 AI 조직에 의해 유사한 증명이 발표되었으나, 본문에 제시된 버전은 문제를 계층의 훨씬 낮은 단계에 위치시키는 반면, OpenAI의 결과는 더 약한 경계 아래에 둔다.

이 발견의 함의는 추상적인 수론의 이론을 훨씬 넘어선다. 이 기하학적 문제를 해결하는 데 사용된 동일한 수학적 도구들은 최적화 및 제어 이론에 사용되는 준정부호 계획(semidefinite programs)의 타당성을 결정하거나, 많은 제곱근의 합을 정수와 비교하는 제곱근 합 문제(square-root sum problem)를 해결하는 등 다른 어려운 문제들에 적용되었다. 연구자는 이러한 문제들 또한 동일하게 관리 가능한 수준의 계산 난이도 안에 놓일 수 있음을 보여주었다. 또한 그는 특정 부호 패턴을 가진 임계점을 세는 방식을 사용하여, 각 해를 개별적으로 찾지 않고도 해의 총 개수를 결정할 수 있음을 입증했다. 이는 이전에는 훨씬 더 어려운 것으로 생각되었던 작업이다.

논문은 또한 불가능한 것에 대해서도 다룬다. 연구자는 자신이 개발한 복잡한 카운팅 메커니즘 없이 더 단순하고 직접적인 접근 방식이 이 문제들을 해결할 수 있다는 아이디어를 신중하게 배제했다. 그는 단일한 증명(certificate)이나 단순한 증거(witness)를 찾으려는 시도와 같은 지름길들이, 해가 너무 복잡하여 짧게 기술할 수 없기 때문에 불충분하다는 것을 보여주었다. 나아가, 그의 방법이 실수에 대해서는 작동하지만 복소수에 대해서는 동일한 방식으로 자동으로 문제를 해결하지 못한다는 점을 입증하며, 두 수학적 세계 사이의 근본적인 차이를 강조했다. 또한 이 작업은 문제가 현재 카운팅 계층의 네 번째 단계에 속하는 것으로 제안되었지만, 반드시 첫 번째 단계에 있는 것은 아니라는 점을 명확히 하며, 여전히 정교한 알고리즘을 필요로 하는 도전적인 문제임을 밝힌다.

궁극적으로 이 연구는 이전에 안개가 자욱했던 영역에 대해 더 명확한 지도를 제공한다. 실수의 존재 이론이 카운팅 계층의 네 번째 단계에 있다고 제안함으로써, 저자는 컴퓨터 과학자와 수학자들에게 계산적으로 달성 가능한 것에 대한 새로운 기준점을 제시했다. 이 작업은 깊은 수학적 질문을 해결하기 위해 인간의 통찰력과 인공지능을 결합하는 힘을 보여주는 증거이다. 이는 무한한 자원을 필요로 하는 것처럼 보이는 문제라도, 어디를 보아야 하고 어떻게 세어야 하는지 안다면 유한하고 셀 수 있는 과정으로 환원될 수 있음을 보여준다. 이 결과는 계산의 한계에 대한 더 정밀한 이해를 제공하며, 기하학적 추론의 세계에서 가능한 것과 불가능한 것 사이의 경계를 더 명확하게 보여준다.