▲

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

 (quantamagazine.org)
25P by GN⁺ 2일전 | ★ favorite | 댓글 1개
  • 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는 결과에 대해 이렇게 회고함:
    “내가 정말로 증명하고 싶은 것을 증명하지는 못했지만, 결국 증명한 것이 내가 원했던 것보다 더 훌륭했어요.”
▲
GN⁺ 2일전  [-]
Hacker News 의견
  • 퍼지(fuzz)를 빼고 말하면, 시간 t에 동작하는 멀티테이프 튜링 머신은 O(sqrt(t log t)) 공간을 이용해 시뮬레이션 가능함 (보통 시간은 t보다 더 오래 걸림) Simulating Time With Square-Root Space
    • Quanta 기사들이 수학에 시적이거나 과장된 표현을 너무 많이 섞어서 오해를 불러일으키는 점이 아쉬움 Quanta 기사에서 “특정 작업들은 실행 시간에 비례하는 만큼의 공간이 필요했다”고 말하지만, 복잡도 위계(hierarchy)만 봐도 그런 일반적 직관이 나오진 않음 “일부 알고리듬”에 국한된 이야기만으로 전체 직관을 만들 순 없음
    • 독자에게 너무 친절한 건지, Quanta가 P 복잡도 클래스를 “합리적인 시간 내에 풀 수 있는 모든 문제”라고만 설명하면서 polynomial이라는 용어 자체를 안 쓴 게 좀 모욕적으로 느껴짐
  • Perl 철학을 담은 “Camel Book”에서 이런 구절이 있음: “메모리가 부족하면 사면 되지만, 시간이 부족하면 방법이 없음” 그저 재미있는 책이라 애정함
    • 이 말도 양면성이 있다는 생각임 컴퓨터 메모리보다 더 필요한 프로그램은 당장 돌릴 수 없는 반면, 오래 걸려도 어쨌든 실행은 할 수 있으니 시간도 결국 중요한 자원임
  • 미리 계산해둔 값들을 저장해둔 룩업 테이블의 승리 예전엔 프로세서가 필요 없을 정도로 모든 연산을 중앙에서 저장할 수 있다면 처리 속도가 혁신될 수 있을 것 같았음 (사실 빠른 검색이라는 별도의 난제 존재)
    • 예전에 저장 시스템 일을 시작할 때 4KB 블록을 미리 전부 계산해서 저장해두자는 아이디어를 냈는데, 고유 4KB 블록 수가 우주의 원자 수보다 많다는 지적을 받고 깜짝 놀랐던 기억임
    • HashLife라는 알고리듬이 Conway의 Game of Life에서 이와 비슷한 작업을 Turing 완전하게 수행함 너무 복잡하고 다양한 상태를 다룰 때도 점프하듯 미래 상태를 미리 계산할 수 있다는 사실이 신기하게 느껴졌음
    • retrieval(검색)룩업 자체도 캐싱한다는 아이디어에는 문제가 없다는 농담
    • 커뮤니티 단위 캐싱, 즉 프리컴파일된 소프트웨어 배포 방식에서 사실상 구현되고 있음 효율적으로 컴파일하지 못해서 언어 기능을 포기해야 한다는 전통적 장벽도, 클라우드 병렬 컴파일과 전세계 캐시로 극복 가능 출시에 한 번만 컴파일 되면 다 함께 쓸 수 있음
    • “중앙에 모든 연산을 저장한다면 프로세서가 필요 없을 것 같다”는 말의 연장선으로, 아예 검색 내역까지 메모이즈해줄 생각임
  • Quanta 스타일이 시적인 탓에 실제로 이 연구가 실질적인 컴퓨터에도 적용 가능한지, 아니면 순수 이론적 시나리오인지 이해하기 어려움 더 많은 메모리를 쓰는 대신 컴퓨터 속도가 느려진다는 의미인지 궁금함
  • raster 그래픽 프로그래밍을 오래 해왔고, 룩업 테이블 활용이 자연스레 몸에 배어 있음 최근엔 여러 도형을 미리 DB에 넣어두고 쿼리 때마다 최적화된 결과를 쓸 수 있는 서버 도구를 개발함 복잡하지 않고 직관적인 패턴임 MIT 교수에게 특별히 배운 것도 아니고 그냥 몸으로 익힌 작업 방식이었는데 수학적으로 정당하단 증거를 보니 뿌듯함 많은 알고리듬적 노하우가 사실 실무자들의 경험에서 비롯될 때도 많다는 생각임 (ex: winding number 알고리듬)
    • 게임의 최적화를 하면서 요즘 얻고 있는 성과는 모두 룩업 테이블을 상황에 맞춰 다루는 방식임 꼭 정적 배열만 룩업 테이블일 필요 없고, 시간에 따라 약간씩 변하는 데이터도 마찬가지로 활용 가능함 GPU에서 작업을 처리하는 쪽으로 눈을 뜨게 됐고, 컴파일 혹은 런타임 때 정적으로 만들어지던 테이블을 런타임 중 일부만 바꿔서 텍스처처럼 GPU로 넘기는 구조에 효율성이 큼 어디까지를 룩업 테이블로 부르느냐의 경계가 흐릿해짐
  • 공간(메모리)이 시간보다 훨씬 많은 결과값을 표현할 수 있다는 점이 직관적으로 느껴짐 테이프 길이 n에서 O(n) 시간 동안 쓸 수 있지만, 2진수 테이프라면 n길이에 2^n가지 구성이 존재함 공간을 제대로 쓰면 시간에 비해 훨씬 많은 표현력이 생긴다고 생각함
    • 내 직관: 셀 하나에 수백 번 계산한 중간 결과가 저장될 수 있음 만약 중간 결과를 저장하지 못하고, 매번 똑같은 걸 다시 계산한다면 효율이 크게 떨어짐 캐시에 0% 히트율이 나오는 상황은 매우 드물고, 대부분은 공간을 활용한 효율화가 가능함 반대로 한 번의 시간으로 수백 개 셀의 공간을 대체하긴 어렵고, 현재 컴퓨팅 구조에선 무한한 SIMD가 불가능함
    • O(1) 메모리 랜덤 접근 가정이 너무 당연시되는데, 실제로는 컴퓨터 크기가 커질수록 접근 비용이 O(n^(1/3))까지 커짐 데이터센터에서 생생히 체감 가능 UMA 말고 다른 모델이었던 걸로 기억남
    • P ≠ PSPACE가 증명되지 않은 만큼, 직관보다 수학적으로 입증하는 게 어려운 영역임
    • 한편으론 맞는 말이지만, 병렬화가 어려운 문제(예: alternating machine PTIME=PSPACE)에서는 공간이 큰 이득을 주지 못할 수도 있음 논문에선 t/log t에서 sqrt(t log t)로의 도약이 혁신적이지만, 무한 병렬화에도 극복되지 않는 실체적 한계가 있을 것임
    • 실무에선 작업 특성에 따라 달라짐 대입 연산보다 저장소 접근이 훨씬 느릴 때는 다시 계산하는 게 빠를 때도 있음
  • 시간-공간 간 “역관계”는 한쪽 자원을 제한할 때, 다른 쪽 최적값을 무조건 얻을 수 없는 현상으로 설명 가능함 예를 들어 정렬 알고리듬에서 시간/공간/안정성 세 가지 제약이 있을 때, 안정성을 추가로 만족하면 오히려 시간이나 공간 효율이 떨어짐 현재까지는 비안정 정렬만큼 빠르고 메모리도 적게 드는 안정 정렬은 없음
  • Quanta Magazine의 기사 스타일이 개인적으로 마음에 듦 컴퓨터 과학자뿐 아니라 관련 분야에 관심 있는 일반인까지 시야를 넓혀줌 조감도와 친근한 설명 방식이 새로운 시각과 아이디어를 주는 계기임
  • Ryan Williams의 강연과 논문을 링크로 공유함
  • single-tape 튜링 머신이 입력으로 이진수 N을 받고, tape 오른쪽에 1을 N개 쓰려고 하면, 시간 N에 N칸 공간이 필요해 보임 그런데 어떻게 N보다 적은 공간에서 이걸 시뮬레이션할 수 있는지 궁금함 tape의 임의 위치로 점프가 불가능한 튜링 머신 구조 특성상 실제 컴퓨터랑 어떤 관계가 있는지도 궁금함
    • 멀티테이프 튜링 머신은 단일 테이프보다 아주 빠르고, 여기서 말하는 “공간”은 입력/출력 제외한 임시 작업 공간임
    • 논문은 결정 문제가 주된 대상으로, 출력이 1비트만 필요한 상황만 고려함 출력이 N비트라면 사실상 N개의 결정 문제를 붙인 것과 동일하다는 설명임
답변달기