NPを超えて：より直感的な複雑性問題

著者は、停止問題をNP困難よりも難しい問題の典型的な例として用いることに異議を唱え、それが混乱を招き、直感的でない点を主張しています。決定不能である一方、「はい」という答えの検証は、プログラムを有限ステップ実行することで行えます。より理解しやすい代替案として、無限グリッド上でトークンを移動させ、目標地点に到達できるかどうかを判断する問題が提示されています。この問題は、低次元ではPSPACE完全ですが、次元の増加に伴い複雑さが爆発的に増大し、最終的にアッカーマン完全になります。これは、NP問題をはるかに超える複雑性を視覚的に示しています。