ما وراء NP: مشكلة تعقيد أكثر بديهية

يتحدى الكاتب استخدام مشكلة الإيقاف كمثال نموذجي لمشكلة أصعب من NP-كاملة، بحجة أنها مربكة وغير بديهية. على الرغم من أنها غير قابلة للحل، إلا أن التحقق من إجابة "نعم" لمشكلة الإيقاف يمكن أن يتم بتشغيل البرنامج لعدد محدود من الخطوات. يتم تقديم بديل أسهل للفهم: نقل قطعة على شبكة غير محدودة للوصول إلى نقطة الهدف. هذه المشكلة هي PSPACE-كاملة في الأبعاد الدنيا، لكن تعقيدها ينفجر مع زيادة الأبعاد، ليصل في النهاية إلى اكتمال آكرمان، مما يدل بصريًا على تعقيد يتجاوز بكثير مشاكل NP.