NC1-완전
병렬 연산이 가능한 회로 복잡도 클래스인 NC1에서 가장 어려운 문제 부류이다. 이 논문에서는 시각적 추적 작업이 이 클래스에 속함을 증명하여, 고정된 깊이의 Transformer 모델이 중간 추론 단계 없이 직접 정답을 도출하는 것이 이론적으로 불가능함을 보여준다.