قائمة أصناف التعقيد

تُعد قائمة أصناف التعقيد في نظرية التعقيد الحسابي من الركائز الأساسية لفهم حدود القدرة الحسابية للخوارزميات والآلات المجردة. تضم هذه الأصناف مجموعات من المشكلات تُصنَّف وفقًا للموارد الحسابية المطلوبة لحلها، مثل الزمن (زمن) أو المساحة (فضاء)، وتُستخدم لتمييز مدى صعوبة المشكلات الرياضية والحاسوبية. من أبرز هذه الفئات P (المشاكل التي تُحل في وقت كثير الحدود)، وNP (المشاكل التي يمكن التحقق من حلولها في وقت كثير الحدود)، وNP-Complete (أصعب مشاكل NP)، وco-NP (مكملات مشاكل NP)، وPSPACE (المشاكل التي تُحل باستخدام مساحة كثير حدودية)، وEXPTIME (المشاكل التي تتطلب وقتًا أُسيًا)، إلى جانب أصناف تعتمد على الحسابات الاحتمالية مثل BPP، والحسابات ذات الذاكرة المحدودة مثل L وNL. تهدف هذه التصنيفات إلى تنظيم العلاقات المنطقية بين فئات المشاكل، وتحليلها من منظور إمكانية الحل أو الاستعصاء الخوارزمي، وتُعد قضية "هل P = NP؟" من أشهر المسائل المفتوحة ضمن هذا الحقل. لمزيد من التفاصيل، راجع أيضًا قائمة مواضيع الحساب والتعقيد، والتي تغطي مفاهيم أوسع في هذا المجال المتشابك.Sipser, M. (2012). Introduction to the Theory of Computation.Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach.Garey, M., & Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness.

تحتوي العديد من فئات التعقيد الحسابي على ما يُعرف بـ "الشريك المشارك" (co-class)، وهو الفئة التي تتكون من مكملات جميع اللغات (المشكلات) الموجودة في الفئة الأصلية. فعلى سبيل المثال، إذا كانت لغة ما L تنتمي إلى فئة NP، فإن المكمل المنطقي لتلك اللغة L — أي مجموعة السلاسل التي لا تنتمي إلى L — تنتمي إلى فئة co-NP. وتُستخدم هذه العلاقة في تصنيف المسائل التي يمكن التحقق من "عدم وجود حل" لها بسهولة، كما هو الحال في التحقق من عدم وجود شهادة لخاصية معينة.

ومع ذلك، لا يعني هذا أن فئة co-NP هي ببساطة المكمل الكامل لفئة NP، إذ توجد لغات ومسائل يُعرف أنها تنتمي إلى كلتا الفئتين معًا (NP ∩ co-NP)، مثل بعض مشاكل النظرية العددية (مثال: اختبار أولية الأعداد)، وهناك لغات أخرى من المعروف أنها لا تنتمي إلى أيٍّ منهما، لا إلى NP ولا إلى co-NP، مما يعكس تعقيد البنية النظرية لهذا الحقل. هذه الفروق الدقيقة تُعد أساسية في تحليل الطبقات العليا للتعقيد، وتدفع الباحثين إلى التساؤل المستمر حول علاقات الاحتواء والتكافؤ بين الفئات.Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach, Cambridge University Press.Sipser, M. (2012). Introduction to the Theory of Computation, Cengage Learning.Papadimitriou, C. (1994). Computational Complexity, Addison-Wesley

تشير عبارة "أصعب المشكلات" ضمن فئة تعقيد معينة إلى تلك المشكلات التي تُعد ممثّلة للفئة بأكملها من حيث الصعوبة، ويُطلق عليها اسم "المشكلات الكاملة" (Complete Problems). يُقصد بذلك أن كل مسألة أخرى ضمن تلك الفئة يمكن إرجاعها إليها (reduce) في وقت كثير الحدود باستخدام تحويل معياري (عادةً ما يكون تحويلًا تقليليًا بولينوميًا). على سبيل المثال، في فئة NP تُعرف المشاكل الكاملة باسم NP-Complete، وهي تلك التي لو وُجدت خوارزمية فعّالة لحل واحدة منها، فإن ذلك يعني وجود خوارزمية فعّالة لحل كل مشاكل NP.

تمثل هذه المشكلات ذروة التعقيد ضمن فئتها، وتُستخدم كمعيار لتحليل المسائل الجديدة: فإذا أمكن تحويل مشكلة جديدة إلى مشكلة كاملة معروفة، فإنها تُصنف ضمن نفس الفئة أو تُعتبر على الأقل "صعبة" بنفس الدرجة. هذه الخاصية تُستخدم على نطاق واسع في تحليل المسائل المستعصية، وهي حجر الزاوية في نظرية التعقيد الحسابي.Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-CompletenessSipser, M. (2012). Introduction to the Theory of ComputationArora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach

 روابط خارجية 

 حديقة أصناف التعقيد - قائمة تضم أكثر من 500 فئة تعقيد وخصائصها

 المراجع 

تصنيف:قوائم متعلقة بالرياضيات
تصنيف:أقسام التعقيد الحسابي
تصنيف:صفحات بترجمات غير مراجعة