획기적인 발견: 계산에 필요한 공간이 극적으로 압축됨

MIT 컴퓨터 과학자 Ryan Williams는 계산 공간과 시간 사이의 절충에 대한 50년간의 가정을 뒤엎는 획기적인 발견을 했습니다. 기존 이론에서는 t단계 계산에 약 t비트의 메모리가 필요하다고 생각했습니다. 그러나 Williams는 t시간 내에 해결할 수 있는 문제라면 약 √t비트의 메모리로 해결할 수 있다는 것을 증명했습니다. 이러한 성과는 문제를 공간을 영리하게 재사용하는 동등한 문제로 변환하여 정보를 압축하는 데 의존합니다. 이 연구는 계산의 병목 현상이 메모리 용량이 아니라 메모리의 효율적인 사용 방법임을 시사합니다.