57. مقدمة إلى فئات التعقيد: P مقابل NP

تصنف فئات التعقيد المشكلات الحاسوبية بناءً على الموارد المطلوبة لحلها. هذا أمر بالغ الأهمية لفهم حدود الحوسبة.

فئة P (Polynomial Time)

P تعني 'وقت حدودي (Polynomial time)'. تتضمن هذه الفئة جميع مشاكل القرار (المشاكل ذات الإجابة بنعم/لا) التي يمكن حلها بواسطة آلة تورينج حتمية (أي، جهاز كمبيوتر قياسي) في وقت حدودي، مما يعني O(N^k) لبعض الثابت k.

• أمثلة: الفرز، البحث، إيجاد شجرة MST.

فئة NP (Non-deterministic Polynomial Time)

تتضمن NP جميع مشاكل القرار التي يمكن التحقق من حلها في وقت حدودي. ملاحظة: NP لا تعني 'Non-Polynomial'.

• إذا سلمك شخص ما حلاً محتملاً لمشكلة NP، يمكنك التحقق بسرعة مما إذا كان صحيحاً.
• مثال: مشكلة البائع المتجول (TSP). إيجاد أقصر طريق صعب، لكن التحقق من أن مساراً مقترحاً أقصر من X سهل.

مشكلة P مقابل NP (سؤال المليون دولار)

هل P = NP؟ هل يمكن أيضاً حل كل مشكلة يكون حلها سريع التحقق بسرعة؟ يعتقد معظم علماء الحاسوب أن P ≠ NP، لكن هذا يظل غير مثبت. مشكلات NP-Complete هي المشكلات 'الأصعب' في NP.