NP를 넘어서: 더 직관적인 복잡도 문제

저자는 정지 문제를 NP-완전보다 어려운 문제의 전형적인 예로 사용하는 것에 이의를 제기하며, 그것이 혼란을 야기하고 직관적이지 않다는 점을 주장합니다. 결정 불가능하지만, "예"라는 답변의 검증은 프로그램을 유한 단계 실행함으로써 수행할 수 있습니다. 더 이해하기 쉬운 대안으로, 무한 그리드에서 토큰을 이동시켜 목표 지점에 도달할 수 있는지 여부를 판단하는 문제가 제시됩니다. 이 문제는 저차원에서는 PSPACE-완전하지만, 차원의 증가에 따라 복잡성이 폭발적으로 증가하여, 결국 아커만 완전에 도달합니다. 이것은 NP 문제를 훨씬 넘어서는 복잡성을 시각적으로 보여줍니다.