알고리듬 연구의 새로운 지평, "약간의 메모리가 많은 시간보다 강력할 수 있다" 증명

• MIT 이론 컴퓨터 과학자 Ryan Williams가 발표한 새 증명은, 메모리 자원이 시간보다 더 강력한 계산 자원일 수 있음을 보임
• 기존의 시간-공간 복잡도 관계에 대한 50년간의 정체를 깨고, 모든 알고리듬을 더 적은 메모리로 변환할 수 있는 방법을 제시
• 증명의 핵심은, 공간 절약 시뮬레이션을 일반화해, 알고리듬의 공간 사용량을 시간의 제곱근 수준으로 줄이는 아이디어
• 이로 인해, PSPACE와 P 클래스의 차이를 정량적으로 입증하는 데 진전을 이루었으며, 더 넓은 간격의 증명으로 이어질 가능성도 열림
• 전문가들은 이 성과를 “놀라운 발전이자 새로운 탐험의 출발점”으로 평가하며, 향후 이 결과가 다른 이론 컴퓨터 과학 난제를 푸는 실마리가 될 수 있음

One Small Step for Space, One Giant Leap for Complexity

Ryan Williams의 새로운 증명 개요

• 2024년 여름, MIT의 Ryan Williams는 자신의 증명을 검토하면서 실수라고 생각했던 아이디어가 실제로 유효하다는 것을 깨달음
• 그는 모든 알고리듬을 더 적은 메모리로 실행 가능하게 변환하는 일반적인 절차를 제안
• 이로 인해, 일부 문제는 제한된 시간으로는 해결할 수 없음을 입증

시간과 공간: 계산의 두 자원

• 모든 알고리듬은 시간과 메모리(공간) 을 사용
• 기존에는 특정 문제 해결 시 공간이 시간에 비례한다고 여겨졌음
• Williams의 증명은 시간보다 공간이 더 강력할 수 있음을 수학적으로 정립

이론 컴퓨터 과학의 시초와 역사

• Juris Hartmanis와 Richard Stearns는 1960년대에 시간/공간 복잡도 정의를 수립
• 이들은 문제를 해결하는 데 필요한 자원에 따라 문제를 복잡도 클래스로 분류하는 기초를 마련
• P는 합리적인 시간 내 해결 가능한 문제, PSPACE는 적절한 메모리로 해결 가능한 문제

최초의 진전: 1975년의 시뮬레이션 기법

• Hopcroft, Paul, Valiant는 모든 알고리듬을 약간 더 적은 공간으로 바꾸는 보편 시뮬레이션 절차를 개발
• 이는 시간과 공간의 연관성을 밝히는 데 첫 발자국이 되었지만, 이후 한계에 부딪힘
• 데이터는 같은 공간을 동시에 차지할 수 없다는 전제 때문에 더 이상 진전 불가하다고 여겨졌음

전환점: Squishy Pebbles

• 2010년, 선구적인 복잡도 이론가 Stephen Cook과 그의 동료들은 트리 평가 문제 - Pebbles and Branching Programs for Tree Evaluation라는 과제를 고안하여, 특정 임계값 미만의 공간 예산을 가진 알고리듬에서는 이 과제가 불가능하다는 것을 증명
  • 하지만 허점이 있었음. 그 증명은 폴과 그의 동료들이 수십 년 전에 내놓았던 것과 같은 상식적인 가정에 기반
  • 즉, 알고리듬은 이미 가득 찬 공간에 새로운 데이터를 저장할 수 없다는 것
  • 10년 넘게 복잡성 이론가들은 그 허점을 메우려고 노력했음
• Stephen Cook의 아들인 James Cook과 Ian Mertz는 2023년에 기존 전제를 깨는 트리 평가 문제 알고리듬을 발표 Tree Evaluation Is in Space 𝑂 (log 𝑛 · log log 𝑛)
• 이들은 메모리 내의 데이터가 물리적으로 중첩 가능하다는 새로운 표현 모델을 제안
• 이 방식은 기존 시뮬레이션 한계를 극복할 수 있는 열쇠가 되었음

Williams의 결정적 도약

• 학생들의 발표를 계기로 Cook-Mertz의 기법을 접한 Williams는, 이를 보편 시뮬레이션에 적용하는 아이디어를 떠올림
• 새로운 시뮬레이션은 알고리듬의 공간 요구량을 시간의 제곱근 수준으로 줄일 수 있음
• 그는 2025년 2월 최종 논문을 arXiv에 게시, 학계의 격찬을 받음

이 결과가 의미하는 것

• 이 증명은 PSPACE > P임을 직접 증명한 것은 아니지만, 그 방향으로 가는 ‘틈’을 만든 결정적 성과
• 앞으로 이 절차를 반복적으로 적용해 더 큰 간극을 만들 수 있다면, P vs PSPACE 문제 해결에 근접 가능
• 이는 컴퓨터 과학의 가장 오랜 난제 중 하나를 푸는 단초가 될 수 있음

여운 있는 결말

• Williams는 결과에 대해 이렇게 회고함:
  “내가 정말로 증명하고 싶은 것을 증명하지는 못했지만, 결국 증명한 것이 내가 원했던 것보다 더 훌륭했어요.”