الرياضيات
هل P تساوي NP؟
أفق بعيدلماذا يهمّ
تسأل المسألة عمّا إذا كانت كل مسألة يسهل التحقق من إجابتها يسهل حلها أيضًا. فإن كان الأمر كذلك، أمكن جدولة النقل على النحو الأمثل لنقل الناس والبضائع بسرعة أكبر وكلفة أقل، لكن تشفير المفتاح العام سيصبح مستحيلًا.
ما نعرفه
طُرحت عام 1971: إذا كان التحقق من مسألة سهلًا، فهل حلّها سهل أيضًا؟
ما يعيقنا
ثبت أن عدة عائلات رئيسية من تقنيات البرهان غير كافية.
المسارات الحالية
نظرية التعقيد الهندسية، والحدود الدنيا للدارات.
أسئلة فرعية
- هل يستطيع أحد أن يبرهن أن مسألة معطاة صراحةً تحتاج إلى دارات بوليانية حجمها أكبر من الخطي؟ أفضل حدّ أدنى معروف هو نحو 4n فقط.
- هل NP مختلفة عن co-NP؟ وبصيغة مكافئة، ألا يوجد أي نظام برهان يعطي براهين قصيرة لكل تحصيل حاصل (tautology)؟
- ما تقنيات البرهان القادرة على تجاوز الحواجز المعروفة لـ«النسبنة» و«البراهين الطبيعية»؟
أسئلة مرتبطة
المصادر
لم يراجعه مختص بعد.
آخر تحقق: 2026-11-18
سجل هذا السؤال
العودة إلى الخريطة ←