نظرية التعقيد الحسابي
تصنف نظرية التعقيد الحسابي المشكلات بناءً على مقدار الوقت والذاكرة والموارد الأخرى التي تحتاجها أي خوارزمية لحلها، وترسم خطوطًا واضحة بين ما يمكن حله بكفاءة وما يبدو أنه مستعصٍ.
Definition
تدرس نظرية التعقيد الحسابي الصعوبة الجوهرية للمشكلات الحسابية المقاسة بالموارد، وبشكل رئيسي وقت التشغيل والذاكرة، المطلوبة لحلها على نموذج مثل آلة تورينج، وتجمع المشكلات في فئات تعقيد وفقًا لذلك.
Scope
يغطي هذا المجال فئات تعقيد الوقت والمساحة مثل P و NP و PSPACE والتسلسل الهرمي متعدد الحدود، ونظرية NP-الكمال (NP-completeness) والاختزالات متعددة الحدود الزمنية، والسؤال المركزي P مقابل NP، والنماذج المحدودة الموارد التي تتضمن العشوائية والتفاعل والبراهين، بالإضافة إلى التسلسل الهرمي ونتائج الصعوبة التي تربط هذه الفئات.
Sub-topics
Core questions
- كم من الوقت والذاكرة يتطلب حل مشكلة معينة بطبيعتها؟
- ما هي المشكلات التي يمكن حلها بكفاءة وما هي المشكلات التي تبدو مقاومة لجميع الخوارزميات الفعالة؟
- كيف يتم إظهار أن المشكلات صعبة مثل أصعب أعضاء فئة التعقيد؟
- هل تضيف العشوائية أو التفاعل أو عدم التحديد قوة حاسوبية حقيقية؟
Key theories
- نظريات التسلسل الهرمي للوقت والمساحة
- بإعطاء وقت أو مساحة أكبر بشكل صارم، يمكن للآلات حل مشكلات أكثر بشكل صارم، مما يثبت أن فئات التعقيد تشكل تسلسلات هرمية حقيقية وأن بعض المشكلات أصعب بطبيعتها من غيرها.
- NP-الكمال (NP-completeness)
- تحدد نظرية كوك-ليفين المشكلات في NP التي تختزل إليها كل مشكلة أخرى في NP، لذا فإن خوارزمية فعالة واحدة لأي منها ستحل جميعها بكفاءة.
- النماذج المحدودة الموارد
- تضيف العشوائية أو التفاعل أو التناوب فئات مثل BPP و IP والتسلسل الهرمي متعدد الحدود، والتي توضح علاقاتها الصورة لما يمكن أن تحققه الموارد الإضافية وما لا يمكنها تحقيقه.
Clinical relevance
توجه نظرية التعقيد الممارسة من خلال التصديق على المشكلات التي تقبل خوارزميات فعالة وتلك التي هي NP-صعبة (NP-hard)، وبالتالي من الأفضل معالجتها بالاستدلالات أو التقريب؛ كما أن الصعوبة المفترضة لمشكلات معينة تدعم التشفير الحديث، الذي تعتمد أمانه على مهام يُعتقد أنها غير ممكنة حسابيًا.
History
أسس هارتمانيس وستيرنز هذا المجال في عام 1965 من خلال تعريف فئات التعقيد وإثبات نظريات التسلسل الهرمي. قدم كوك وليفين NP-الكمال (NP-completeness) حوالي عام 1971، وأظهر كارب العديد من المشكلات الطبيعية الكاملة في عام 1972، وأضافت العقود التالية نماذج براهين عشوائية وتفاعلية وقابلة للتحقق احتماليًا.
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- ما الفرق بين القابلية للحساب والتعقيد؟
- تسأل القابلية للحساب عما إذا كان يمكن حل مشكلة ما بواسطة أي خوارزمية على الإطلاق، متجاهلة التكلفة. يفترض التعقيد أن المشكلة قابلة للحل ويسأل عن مدى تكلفة هذا الحل من حيث الوقت والذاكرة، ويرسم تمييزات أدق بين المشكلات القابلة للحل من حيث المبدأ.
- لماذا يعتبر NP-الكمال (NP-completeness) مهمًا في الممارسة؟
- عندما يتبين أن مشكلة ما هي NP-كاملة، فإنها ترتبط بآلاف المشكلات الأخرى التي لا توجد لها خوارزمية فعالة معروفة على الرغم من عقود من الجهد. يشير هذا إلى أن البحث عن خوارزمية دقيقة سريعة قد يكون عقيمًا وأن التقريب أو الاستدلالات أو طرق الحالات الخاصة هي المسار الواقعي.