알고리듬에서 약간의 메모리가 많은 시간을 능가함

4 weeks ago 11

P와 PSPACE는 각각 시간과 공간 복잡도에 기반한 주요 복잡도 클래스임
이 두 클래스의 관계는 컴퓨터 과학에서 가장 핵심적인 미해결 문제 중 하나임
1975년 Hopcroft, Paul, Valiant가 보편적 시뮬레이션 기법으로 약간의 공간 절약법을 제시함
아직까지도 공간-시간 사이의 절대적 경계에 대한 의문이 남아 있음
최근까지도 근본적 한계 또는 다른 해법의 필요성에 대한 논의가 지속 중임

P와 PSPACE 클래스에 대한 소개

P 클래스는 현실적으로 해결 가능한 시간 내에 풀 수 있는 모든 문제를 포함하는 중요 복잡도 클래스임
PSPACE는 공간(메모리) 관점에서 정의되는 유사한 복잡도 클래스임
모든 P 문제는 PSPACE에도 포함되며, 즉 빠른 알고리듬은 많은 공간을 필요로 하지 않음
만약 반대도 성립한다면, 공간과 시간의 계산 능력이 동등함을 의미함
이론적으로 PSPACE가 P보다 훨씬 크다고 복잡도 이론가들은 추측함
공간은 반복적으로 활용 가능하지만, 시간은 한 번 지나면 되돌릴 수 없다는 점 때문에 공간의 계산 자원 가치가 더 높음

공간 시뮬레이션 연구의 시작: A Space Odyssey

복잡도 이론에서 P와 PSPACE의 관계 규명이 큰 논점임
Cornell 대학교에서 Hartmanis 지도 하에 Hopcroft와 Paul이 시간과 공간 사이의 정확한 관계를 연구함
P 대 PSPACE 문제 해결에는, 주어진 시간 내에는 특정 계산이 불가능함을 입증해야 하지만, 이는 일반적으로 어렵기 때문에, 연구자들은 시각을 전환하여 제한된 공간 내에서 무엇을 할 수 있는지 탐구함
이들은 시뮬레이션 기법을 사용하여, 모든 알고리듬에 대해 공간과 시간을 교환하는 보편적인 변환이 가능한지 연구함
- 예를 들어, 매우 빠른 책정렬 알고리듬이 공간을 많이 요구한다면, 더 느리지만 공간을 덜 사용하는 변환이 존재하는지 탐구함
- 알고리듬 전체에 적용 가능한 보편적 시뮬레이션 방법이 당시에는 존재하지 않았음
1975년 Hopcroft, Paul, Leslie Valiant가 합류하여, 모든 알고리듬에 대해 기존 시간 예산보다 약간 더 작은 공간 예산으로 동등한 결과를 내는 새로운 알고리듬을 만들어내는 보편적 시뮬레이션 방법을 고안함
- Valiant는 "주어진 시간만큼 필요한 모든 계산은, 그보다 적은 공간으로도 가능함"이라고 설명함
- 이 방식은 시공간 상호관계 연구에 최초로 중요한 돌파구를 마련함
그러나 이 연구는 곧 한계에 봉착함
- 보편적 시뮬레이션 방식이 모든 경우에서 공간 절약 효과가 크지 않거나 불가능한 상황이 발견됨
- Paul 등은, 명백한 가정(동일한 데이터 조각이 동시에 같은 메모리 공간을 차지할 수 없다는 전제) 하에 더 나은 보편적 시뮬레이션은 불가능함을 증명함
- 이에 따라 P vs PSPACE 문제 해결은 시뮬레이션 대신 전혀 다른 방법 접근이 필요하다는 결론에 가까워짐