مشكلة «بي = إن-بي؟» هي من أبرز مسائل القرن في علوم الحاسوب النظرية وتطرح سؤالين متقابلين: هل كل مسألة يمكن التحقق من صحة حلها بكفاءة زمنية متعددة حدودية يمكن أيضًا حلها بكفاءة زمنية متعددة حدودية؟ الحل الحاسم يتطلب إما بناء خوارزمية عامة تَحوِّل حُلولَ الاختبار إلى حلول فعالة لجميع مسائل فئة «إن-بي»، أو إثبات حدود زمانية صارمة تفصل بين الفئتين بإظهار أن بعض مسائل «إن-بي» لا تقبل حلولًا زمنية تعددية حدود لأي خوارزمية حاسوبية. المفاتيح البحثية الأساسية تتضمن تطوير أدوات لإثبات حدود التعقيد الحسابي، خاصة إثبات حواجز زمنية أو قيود على الدوائر الحاسوبية، وتجاوز عقبات نظرية معروفة مثل حدود «التقطيع الذاتي» و«التفهيم المتعلق بالنسخ» وقيود البرهان الطبيعي؛ كما تشمل دراسة البنيات العودية والتحولات المحوسبة وتحليل صعوبة مسائل «إن-بي-الكاملة». تحقيق تقدم يتطلب تقنيات جديدة لبرهنة انخفاض تعقيد أو لإيجاد تعميم خوارزميات فعالة، لأن الطرق التقليدية أثبتت محدوديتها في حل المشكلة بشكل قاطع.