알고리즘 시뮬레이션의 지각 변동: 메모리 돌파구

획기적인 연구 결과가 알고리즘 시뮬레이션의 기반을 뒤흔들었습니다. Ryan Williams의 새로운 연구는 모든 알고리즘을 원래 실행 시간보다 훨씬 적은 메모리를 사용하여 시뮬레이션할 수 있음을 보여줍니다. 이는 이전 최고 결과를 훨씬 뛰어넘는 개선입니다. 이 돌파구는 Cook과 Mertz의 공간 효율적인 트리 평가 알고리즘을 활용하여 튜링 머신 계산을 영리하게 분할하고 유한체 인코딩을 사용하여 공간 복잡도를 거의 2배로 개선합니다. 시간 제한은 유지되지 않지만, 이 획기적인 결과는 복잡도 이론에 큰 영향을 미치며 공간 복잡도 상한의 추가 감소 등 미래 연구의 길을 열어줍니다. P와 PSPACE 복잡도 클래스의 분리로 이어질 가능성도 있습니다.