1조 단계짜리 계산을 다시 하려면 메모리가 얼마나 필요할까요 — 50년 동안 답을 너무 크게 잡고 있었습니다

계산에는 두 가지 예산이 듭니다. 시간과 메모리요. 그런데 이 둘은 성질이 아주 다릅니다 — 시간은 한 번 쓰면 돌아오지 않지만, 메모리는 지우고 다시 쓸 수 있어요. 이 뻔한 비대칭이 얼마나 큰 차이를 만드는지는 50년 동안 잘 몰랐습니다. 2025년 2월에 답의 일부가 나왔는데, 예상보다 훨씬 극적이었습니다.

먼저 문제를 손에 잡히게 놓아 볼게요. 어떤 프로그램이 t단계를 돌아 답을 냅니다. 이 프로그램이 무슨 일을 하는지는 묻지 않습니다. 그냥 t단계 걸린다는 것만 압니다. 이때 같은 답을 얻는 데 메모리가 얼마나 있으면 충분할까요?

가장 순진한 답은 t칸입니다. 매 단계 무슨 일이 있었는지 다 적어 두면 되니까요. 계산 과정을 통째로 공책에 옮겨 적는 셈입니다. 그런데 조금만 생각해 보면 이건 낭비 같습니다. 계산 중간에 적어 둔 값들 중에는 다시는 안 쓸 게 잔뜩 있을 테니까요. 어디까지 지워도 될까요?

01시간과 메모리는 대칭이 아닙니다

이 질문이 왜 어려운지부터 짚고 가야 합니다.

메모리를 아끼는 방법은 사실 늘 하나 알고 있습니다. 필요할 때마다 다시 계산하는 것이요. 값을 저장해 두는 대신, 그 값이 필요해지면 처음부터 다시 만들어 냅니다. 메모리는 거의 안 들고, 대신 시간이 폭발합니다. 이걸 아주 거칠게 밀어붙이면 메모리를 극단적으로 줄일 수는 있는데, 시간이 지수적으로 늘어나 버려요. 그래서 이 방향은 답이 아닙니다.

반대로 시간을 아끼는 방법도 하나 있습니다. 다 저장해 두고 다시 안 계산하는 것이요. 그게 위에 적은 t칸짜리 순진한 답입니다.

그러니 진짜 질문은 이겁니다 — 시간을 터무니없이 늘리지 않으면서, 메모리를 어디까지 내릴 수 있나. 그리고 여기서 앞에 적은 비대칭이 힘을 씁니다. 계산이 지나간 시간 t단계는 되돌릴 수 없지만, 메모리 한 칸은 같은 계산 안에서 몇 번이고 다시 쓰일 수 있습니다. 직관적으로 메모리가 더 강력한 자원이어야 한다는 뜻이에요. 문제는 얼마나 더 강력하냐는 걸 아무도 몰랐다는 겁니다.

021975년, 그리고 멈춰 있던 50년

1975년에 존 호프크로프트, 볼프강 폴, 레슬리 발리언트가 첫 답을 내놓습니다. 1977년 Journal of the ACM에 실린 제목이 그대로 「On Time Versus Space」예요(1975년 FOCS 발표 때 제목은 「On Time versus Space and Related Problems」였습니다).

이들이 보인 것은 t단계짜리 계산은 t / log t 칸의 메모리로 다시 해낼 수 있다는 것이었습니다. 여기서 log는 밑이 2인 로그고, 이건 개별 알고리즘을 손보는 이야기가 아니라 모든 계산에 통째로 적용되는 변환입니다. 어떤 프로그램을 가져와도 이 방법으로 메모리를 줄인 판본을 만들 수 있어요.

그런데 t / log t가 얼마나 줄인 걸까요. 솔직히 말하면 별로입니다. t가 1조일 때 log t는 40쯤이니까, 메모리가 40분의 1로 줄었습니다. 나쁘지 않지만 여전히 t에 비례해서 늘어나요. 계산이 열 배 길어지면 메모리도 대충 열 배 필요합니다. 성격이 바뀌지 않은 개선입니다.

그리고 여기서 50년이 멈춥니다. 더 줄일 수 있다는 낌새가 안 보였을 뿐 아니라, 이 접근으로는 더 못 줄인다는 걸 시사하는 결과들이 쌓였어요. 그래서 이 방향은 조용히 닫힌 서랍처럼 남았습니다. 교과서에는 실렸지만 아무도 다시 열지 않는.

03도구는 엉뚱한 서랍에서 나왔습니다

2025년 2월 25일, MIT의 라이언 윌리엄스가 논문 한 편을 올립니다. 제목은 「Simulating Time With Square-Root Space」, 우리말로 옮기면 「제곱근 공간으로 시간을 시뮬레이션하기」입니다.

주 정리는 한 줄입니다.

여기서 하나만 못 박아 두겠습니다. 이건 상한입니다. √(t log t)면 충분하다는 뜻이지, 그보다 적게는 쓸 수 없다는 뜻이 아니에요. 실제로 얼마가 있어야만 하는지 — 그러니까 하한 쪽은 여전히 거의 아무것도 모릅니다. 이 글의 숫자들도 전부 "이만큼이면 된다" 쪽입니다.

t / log t 에서 √(t log t) 로 내려왔습니다. 이게 왜 성격이 다른 개선인지는 히어로 그림이 말해 줍니다 — 가로가 로그 눈금이라, 제곱근을 취하면 막대 길이가 정확히 절반이 됩니다. 1975년 막대는 아무리 t를 키워도 맨 위 막대에 거의 붙어 있는데, 2025년 막대는 절반 지점에 가 있어요. 지수가 반으로 접힌 겁니다.

흥미로운 건 이 증명이 시간-공간 문제를 정면으로 파고들어 나온 게 아니라는 점입니다. 도구가 옆 서랍에서 왔어요.

그 서랍의 이름은 트리 평가(Tree Evaluation)입니다. 이런 문제예요 — 뿌리부터 잎까지 뻗은 나무 모양의 계산이 있고, 각 마디는 자기 자식들의 값을 받아 정해진 규칙으로 자기 값을 계산합니다. 잎의 값은 주어져 있고, 우리는 뿌리의 값을 알고 싶습니다. 학교에서 그리는 계산 트리 그대로입니다.

순진하게 풀면 메모리가 이렇게 듭니다. 뿌리 값을 알려면 왼쪽 자식 값을 먼저 구해야 하고, 그걸 어딘가 적어 둔 채로 오른쪽 자식 값을 구하러 내려가야 합니다. 트리 깊이만큼 값이 쌓여요. 오랫동안 사람들은 이게 피할 수 없다고 봤습니다. 값 하나를 놓아두는 자리와 다른 값을 계산하는 자리는 서로 침범하면 안 되니까요.

2024년, 제임스 쿡과 이언 머츠가 그 전제를 깼습니다. 이들의 알고리즘은 값들을 같은 메모리 칸에 겹쳐서 둡니다. 값을 대수적으로 인코딩해 두면, 새 계산의 결과를 그 칸에 더해 넣었다가 나중에 정확히 빼내 원래 상태로 되돌릴 수 있거든요. 저장해 둔 값이 잠식되지 않으면서도 그 칸이 계산에 동원됩니다. 그렇게 트리 평가를 O(log n · log log n) 공간에 넣었어요. 원래 이 분야는 저장된 값 하나하나를 각자 자리를 차지하는 조약돌로 그렸습니다 — 스티븐 쿡의 하한이 그 그림 위에 서 있었고요. Quanta에 인용된 워싱턴대의 폴 빔은, 이제 그 조약돌들을 서로 위에 조금 눌러 겹칠 수 있는 것으로 생각하면 된다고 말합니다. 꽤 좋은 그림이라고 생각해요.

윌리엄스가 한 일은 이 도구를 알아본 겁니다. 그는 임의의 시간 t짜리 계산을 시간 블록으로 잘라 — 이 발상 자체는 1975년 논문에서 가져왔습니다 — 블록 사이의 정보 흐름을 방향 그래프로 그린 다음, 그 그래프를 푸는 문제를 트리 평가 문제 여러 개로 바꿔 놓습니다. 그리고 거기에 쿡·머츠 알고리즘을 붙였어요. 블록 크기를 잘 고르면 √(t log t)가 떨어집니다.

이 논문은 그해 6월 STOC 2025에서 최우수 논문상을 받았습니다.

04직접 밀어 보기 — 세 개의 막대

말로 하면 "제곱근"이 얼마나 큰지 잘 안 잡힙니다. 계산 길이를 직접 바꿔 보세요.

t를 키울수록 격차가 벌어지는 게 보일 겁니다. 10억 단계에서 이미 190배쯤이고, 1조 단계면 4000배 가까이, 100경 단계로 가면 200만 배를 넘습니다. 1975년 막대는 끝까지 맨 위에 붙어 다니는데 2025년 막대만 혼자 절반 근처에 남아요. 이게 성격이 다른 개선의 뜻입니다.

05그런데 이 방법은 훨씬 느립니다

여기서 정직해야 할 대목이 나옵니다. 그리고 이 글에서 제일 중요한 절이기도 합니다.

이 결과를 소개하는 글 중에 "이제 컴퓨터가 램을 훨씬 덜 써도 된다"는 쪽으로 읽히게 쓴 것들이 있습니다. 그건 아닙니다.

1절에서 적은 원리를 다시 떠올려 보세요. 메모리를 아끼는 방법은 저장 대신 재계산이었죠. 윌리엄스의 시뮬레이션도 결국 그 거래를 훨씬 영리하게 하는 것이고, 거래인 이상 대가가 있습니다. 메모리를 √t로 접는 대신 계산은 훨씬 오래 걸립니다.

근거는 논문 안에 있습니다. 쿡·머츠 절차는 트리의 마디마다 함수의 저차 확장을 계산해야 하는데, 논문 5절이 그 비용을 적어 둬요 — b단계짜리 시간 블록 하나에 2^Θ(b) 시간이 듭니다. 여기서 블록 크기가 √t 수준이니(논문이 b를 √(t log t)로 잡습니다), 시뮬레이션에 드는 시간은 2^Θ(√t) 수준으로 뜁니다. t 자체에 대한 지수는 아니지만, 실용과는 거리가 아주 먼 숫자예요.

다만 정확히 해 두면, 논문은 시뮬레이션의 시간 비용을 정리로 명시하지는 않습니다. 관심사가 공간이거든요. 오히려 시간과 공간을 함께 절충할 수 있는지를 열린 문제로 남겨 둡니다. 그리고 Quanta도 이 시뮬레이션이 실용적 응용을 갖기는 어렵다고 정리하고요.

모델도 짚어 둘 필요가 있습니다. 여기서 말하는 계산은 다중테이프 튜링 기계이고, 공간은 그 기계가 쓰는 테이프 칸 수입니다. 이론에서 쓰는 표준 모델이지 여러분 노트북의 램이 아니에요. 이 두 가지를 뭉개면 없는 이야기가 만들어집니다.

그럼 왜 대단한 결과일까요. 이건 알고리즘 소식이 아니라 지도 소식이기 때문입니다. 시간과 메모리라는 계산의 두 기본 자원 사이의 관계가 반세기 만에 다시 그려진 거예요. 이런 정리가 당장 하는 일은 프로그램을 빠르게 만드는 게 아니라, 무엇이 불가능한지를 좁히는 겁니다. 다음 절이 그 이야기고요.

06P 대 PSPACE에는 무엇이 붙었을까요

이 결과가 "P 대 PSPACE 문제에 진전을 냈다"고 소개되는 걸 보셨을 수 있습니다. 정확히 무엇이 붙었는지 따져 보겠습니다.

먼저 상한이 있으면 하한이 따라 나오는 구조를 알아야 합니다. 공간 위계 정리라는 게 있어서, 공간을 더 주면 정말로 더 많은 문제를 풀 수 있다는 건 이미 압니다. 그런데 윌리엄스의 정리는 "시간 t면 공간 √(t log t)로 된다"고 말하죠. 이 둘을 겹치면 공간은 넉넉한데 시간은 부족한 자리가 강제로 생깁니다. 논문이 얻은 따름정리가 그겁니다.

풀어 쓰면 이렇습니다 — 메모리 n칸으로는 풀리는데, 시간은 n²에 육박하게 드는 문제가 실제로 존재한다. 그리고 그런 문제를 구체적으로 지목할 수도 있습니다 — 따름정리 1.3이 선형 공간 완전 언어 하나를 집어 줍니다. 논문의 표현으로는 "선형 공간에 대한 임의의 완전 문제는 이차 시간을 요구한다"예요. 계산복잡도에서 이런 무조건적 하한은 정말 드뭅니다. 가정 없이 "이 문제는 이만큼의 시간이 반드시 든다"고 말할 수 있는 경우가 손에 꼽아요.

그럼 P ≠ PSPACE가 증명된 걸까요. 아닙니다. 그건 여전히 열려 있습니다.

논문이 적어 둔 건 이런 이야기입니다. 만약 정리 1.1을 모든 ε > 0에 대해 TIME[t] ⊆ SPACE[t^ε]까지 밀어붙일 수 있다면, 그때는 P ≠ PSPACE가 따라 나옵니다. 제곱근은 ε = 1/2 한 점을 잡은 것이니, 관건은 그 지수를 0 쪽으로 더 내릴 수 있느냐입니다.

다만 방향을 헷갈리면 안 됩니다. 이건 논문이 제시한 충분조건이지, P와 PSPACE를 가르는 유일한 길이라는 뜻이 아닙니다. 논문 자신은 이 재귀적 확장이 가능한지를 열린 문제로 남겨 두면서, 쿡·머츠 절차의 구조상 그대로는 재귀가 되지 않는다고 적어요. 분명한 건 제곱근 하나로는 두 종류가 갈라지지 않는다는 것뿐입니다.

Quanta의 정리가 정확합니다 — 윌리엄스가 만든 것은 공간과 시간 사이의 정량적 간극이고, P와 PSPACE를 가르려면 그 간극을 훨씬, 훨씬 더 벌려야 한다는 것이죠. 이 결과는 그 방향으로 한 칸 간 겁니다. 큰 한 칸이지만 한 칸이요.

07그 뒤에 일어난 일

이 이야기에는 짧은 후일담이 있고, 저는 이 대목이 결과 자체만큼 마음에 듭니다.

논문에 남은 군더더기는 √(t log t)의 log t입니다. 깔끔한 답은 그냥 √t겠죠. 윌리엄스는 이걸 없애는 조건도 적어 뒀습니다 — 트리 평가를 로그 공간에 넣을 수 있다면 √t가 바로 따라 나옵니다. 그러니 다음 목표가 어디인지는 모두에게 분명했어요.

2025년 8월, 그 log를 없앴다고 주장하는 프리프린트가 arXiv에 올라옵니다. 두 번 개정됐고요. 그리고 2026년 1월 1일, 저자 본인이 철회했습니다. 철회 사유가 그대로 붙어 있어요 — 주 정리의 증명이 틀렸고, 자기 논문의 틀이 윌리엄스의 시뮬레이션에서 생기는 트리 평가 사례들을 제대로 모형화하지 못한다고요. 남이 잡아낸 게 아니라 스스로 찾아 내리고, 무엇이 틀렸는지 공개해 두었습니다.

그래서 지금 상황은 이렇습니다. √(t log t)는 서 있고, √t는 열려 있습니다. 그리고 이 분야가 살아 있다는 증거가 하나 더 남았고요.

수업에서 학생들이 자주 묻는 게 있습니다. 수학은 다 밝혀진 거 아니냐고요. 저는 이 이야기를 꺼낼 생각입니다. 1975년에 적힌 답이 2025년에 바뀌었고, 그 답을 더 밀려던 시도가 넉 달 반 만에 틀린 걸로 판명나 스스로 내려갔습니다. 지금 이 순간에도 아무도 모르는 칸이 남아 있어요.

LOGIC 논리 게이트윌리엄스의 따름정리 하나가 회로 이야기입니다 — 팬인이 제한된(입력 두 개짜리) 게이트 s개 회로는 √s·poly(log s) 공간으로 값을 낼 수 있어요. 그 회로가 어떻게 생겼는지부터 → BIT 아날로그와 디지털 신호이 글이 세는 '칸'은 결국 0과 1이 들어앉는 자리입니다 — 연속인 신호가 칸으로 나뉘는 지점 →

제가 이 결과에서 가장 좋아하는 건 증명 기법이 아니라 서랍이 잘못 닫혀 있었다는 사실입니다. 50년 동안 아무도 이 문제가 풀릴 거라 기대하지 않았는데, 정작 열쇠는 옆방에서 다른 문제를 풀던 사람들이 만들고 있었어요. 윌리엄스가 한 일의 상당 부분은 그 열쇠를 알아본 겁니다. 과학에서 이런 일은 생각보다 자주 일어나고, 그래서 "이 분야는 끝났다"는 말은 대체로 이르다고 생각합니다.

이 글의 근거 — 1차 자료와 확인 범위

1. 본 논문. Williams, R. R. (2025). Simulating Time With Square-Root Space. arXiv:2502.17779 [cs.CC], 제출 2025-02-25(v1). 학회판은 Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), DOI 10.1145/3717823.3718225. 초록·정리·따름정리는 arXiv 판본을 직접 확인했습니다.
2. 본문에서 논문으로 확인한 것. 주 정리(Theorem 1.1) TIME[t(n)] ⊆ SPACE[√(t(n) log t(n))], 모든 t(n) ≥ n · 따름정리 1.2 SPACE[s(n)] ⊄ TIME[s(n)^2−ε](공간 구성 가능한 s(n) ≥ n, 모든 ε > 0) · 따름정리 1.3의 선형 공간 완전 언어에 대한 n^2−ε 시간 하한(논문 표현은 "선형 공간에 대한 임의의 완전 문제"이며, 논문은 "PSPACE-완전"이라는 말을 쓰지 않습니다) · 초록의 "팬인이 제한된 크기 s 회로를 √s · poly(log s) 공간에서 평가" · 정리 1.1이 모든 ε > 0에 대해 TIME[t] ⊆ SPACE[t^ε]로 확장되면 P ≠ PSPACE가 따라 나온다는 서술(§1, §5 — 충분조건이며 논문은 이 확장을 열린 문제로 둡니다) · 5절의 저차 확장 계산 비용 2^Θ(b)와 시간-공간 절충 열린 문제 · 트리 평가가 로그 공간에 들어가면 √t가 따라 나온다는 서술(Corollary 3.6) · 증명 구조(블록 존중 계산 → 블록 간 정보 흐름을 나타내는 방향 비순환 그래프 → 암묵적으로 정의된 트리 평가 사례들 → 쿡·머츠 알고리즘 적용) · 블록 분할 발상이 호프크로프트·폴·발리언트에서 온 것이라는 서술.
3. 상한과 하한의 구분. 정리 1.1은 상한입니다 — √(t log t)면 충분하다는 뜻이지, 그보다 덜 쓸 수 없다는 뜻이 아닙니다. 본문(3절)에서 접힘 밖에 따로 적어 둔 이유입니다. 이 글의 모든 수치는 "이만큼이면 된다" 쪽이고, 하한에 대해서는 아무 주장도 하지 않습니다. 시뮬레이션의 시간 비용도 정리로는 명시되지 않습니다(논문의 관심사가 공간입니다). 다만 5절에 시간 블록 b단계마다 저차 확장 계산에 2^Θ(b) 시간이 든다는 서술이 있어, 본문 5절의 "훨씬 느리다"는 논문으로 뒷받침됩니다.
4. 저자 발언과 대중 해설. Quanta Magazine, For Algorithms, a Little Memory Outweighs a Lot of Time(2025-05-21). 여기서 옮긴 것과 그 출처를 갈라 둡니다. 이 글이 옮긴 윌리엄스의 직접 인용은 한 곳뿐입니다(기사에는 그의 직접 발언이 여럿 더 있습니다) — 1절 인용 상자의 "직관은 정말 단순합니다. 공간은 재사용할 수 있지만, 시간은 그럴 수 없거든요"가 기사 안 그의 직접 발언이고, 번역은 제가 했습니다. 반면 결과로 나오는 알고리즘이 훨씬 느리고 실용적 응용을 갖기 어렵다는 것과 P 대 PSPACE를 얻으려면 간극을 훨씬 더 벌려야 하며 만만찮은 과제라는 것은 기사 본문의 서술이지 윌리엄스의 직접 발언이 아닙니다 — 본문에서도 "Quanta의 정리"로 표시했습니다. 쿡·머츠의 기법을 눌러 겹칠 수 있는 조약돌에 비유한 대목은 기사에 인용된 워싱턴대 폴 빔의 발언이고, 조약돌이라는 틀 자체는 스티븐 쿡의 페블링 하한에서 온 것이라고 기사가 밝힙니다. 논문의 표현이 아닙니다.
5. 1975년 결과. Hopcroft, J. E., Paul, W. J., Valiant, L. G. On Time Versus Space. Journal of the ACM 24(2), 332–337 (1977). 학회 발표는 FOCS 1975. 결과는 시간 t(n)짜리 결정적 다중테이프 튜링 기계를 테이프 복잡도 t(n)/log t(n)으로 시뮬레이션할 수 있다는 것입니다. 본문의 "50년"은 FOCS 1975 → arXiv 2025-02의 간격이고, 윌리엄스 논문 초록도 50년이라고 적습니다.
6. 트리 평가 알고리즘. Cook, J., Mertz, I. Tree Evaluation Is in Space O(log n · log log n). STOC 2024. 이 결과는 학회 발표 전부터 프리프린트로 돌았고 Quanta 기사는 2023년으로 적습니다 — 본문에서는 출판 학회인 2024년을 기준으로 썼습니다. 값을 겹쳐 쓰고 되돌린다는 설명은 이 알고리즘의 핵심 착상을 옮긴 것이며, 대수적 인코딩의 구체적 형태는 본문에서 다루지 않았습니다.
7. 수상 확인. ACM SIGACT STOC Best Paper Award 목록에서 2025년 수상작 4편 중 하나로 확인했습니다. 목록에 실린 제목은 「Simulating Time in (Nearly) Square-Root Space」로 arXiv 판본 제목과 표기가 다릅니다 — 같은 논문이며, 본문에서는 arXiv 제목을 썼습니다.
8. 철회된 후속 프리프린트. arXiv:2508.14831(v1 2025-08-20, v2 2025-08-24, v3 2025-11-13, v4 2026-01-01 철회). TIME[t] ⊆ SPACE[O(√t)]를 주장했고, 철회 사유는 저자 본인이 남긴 것으로 주 정리의 증명이 틀렸으며 논문의 트리 높이 압축·평가 틀이 윌리엄스 시뮬레이션에서 생기는 트리 평가 사례와 의존 관계를 올바로 모형화하지 못한다는 내용입니다. 동료평가를 거치지 않은 프리프린트이고 현재 유효한 결과가 아니므로 본문의 어떤 주장도 여기에 기대지 않았습니다. 저자 이름은 적지 않았습니다 — 스스로 오류를 찾아 철회한 사례라 개인을 지목할 이유가 없다고 봤습니다.
9. 인터랙션의 정체. 막대 길이와 숫자는 t / log t 와 √(t log t)를 밑이 2인 로그로 그대로 계산한 값입니다(계산복잡도의 관례). 다만 두 식 모두 O(·) 상한이라 숨은 상수가 있고, 따라서 표시되는 값은 실제 테이프 칸 수가 아니라 증가 속도의 비교로 읽어야 합니다. 맨 위 "전부 기록" 막대는 정리가 아니라 t칸이라는 순진한 기준선이고, 막대 가로는 log₁₀(값) / log₁₀(t) 비율로 그렸습니다 — 그래서 √t가 정확히 절반 자리에 오고 2025년 막대가 그 선을 조금 넘습니다.
10. 한국어 공백 확인. 한국어로 검색했을 때 이 결과를 다룬 해설을 찾지 못했습니다 — 검색에 잡히는 것은 일반적인 시간복잡도·공간복잡도 개념 글이었습니다. 전수 조사는 아닙니다. 어딘가 있을 수 있고, 다만 제가 확인한 범위에서는 한국어 상세 해설이 비어 있었습니다.
11. "60년 된 질문"의 기준. 시간·공간을 계산 자원으로 정의한 창립 논문은 Hartmanis, J. & Stearns, R. E., On the Computational Complexity of Algorithms, Transactions of the AMS 117, 285–306 (1965)이고, 공간(메모리) 쪽은 Stearns, Hartmanis & Lewis, Hierarchies of Memory Limited Computations(SWCT 1965, 179–190)입니다. 본문 1절의 "60년"은 이 1965년 기준이고, 제목과 2절의 "50년"은 호프크로프트·폴·발리언트(1975) 기준입니다 — 두 숫자의 기준이 다릅니다.
12. 표기에 대하여. TIME[t]·SPACE[s]는 각각 시간·공간 복잡도 종류를 뜻하는 표준 기호로 원문 그대로 두었습니다. 인명은 Ryan Williams 라이언 윌리엄스, Hopcroft·Paul·Valiant 호프크로프트·폴·발리언트, Cook·Mertz 쿡·머츠로 옮겼습니다. block-respecting computation은 블록 존중 계산, Tree Evaluation은 트리 평가로 옮겼습니다.