50년간의 난제, 계산 복잡도 이론의 시간 대 공간 문제 해결

계산 복잡도 이론의 핵심 질문 중 하나는 P와 PSPACE의 관계입니다. P는 합리적인 시간 내에 해결 가능한 문제의 클래스이고, PSPACE는 합리적인 공간 내에 해결 가능한 문제의 클래스입니다. 직관적으로 공간은 시간보다 더 강력한 자원입니다. 왜냐하면 공간은 재사용 가능하기 때문입니다. 50년 동안 연구자들은 PSPACE가 P보다 크다는 것을 증명하려고 노력해 왔습니다. 즉, 빠른 알고리즘으로는 해결할 수 없지만 제한된 공간으로는 해결할 수 있는 문제가 존재한다는 것을 증명하려고 했습니다. Hopcroft, Paul, Valiant는 1975년에 획기적인 발견을 이루어 공간이 시간보다 약간 더 강력하다는 것을 보였습니다. 하지만 이러한 진전은 '시뮬레이션' 접근 방식의 한계에 의해 제한되었습니다. Ryan Williams가 마침내 오랜 난제를 해결하는 혁신적인 접근 방식을 고안했습니다.