سياق مختلف أصناف التعقيد.
في نظرية التعقيد التحسيبي ، صنف التعقيد complexity class هي مجموعة من المسائل المتشابهة في تعقيد مواردها التحسيبية. ولكل صنف تعقيد تعريف من الشكل:
- مجموعة من المسائل التي يمكن حلها عن طريق آلة مجردة باستخدام
على سبيل المثال ، يضم صنف إذا پي مجموعة من مسائل القرار التي يمكن حلها من قبل آلة تورنگ لابترية في زمن كثير حدودي ، بينما يضم صنف PSPACE مجموعة من مسائل القرار التي يمكن حلها باستخدام آلة تورنگ البترية في فراغ كثير حدودي.
تعهد فئات التعقيد الأبسط وفقاً للعوامل التالية:
- نوع المسألة التحسيبية: أكثر المسائل المستعملة مسائل القرار. ورغم ذلك، يمكن تعريف أصناف التعقد على أساس مسائل التوابع (مثال ذلك إف پي)، مسألة عد (تعقيد) (على سبيل المثال شارب پي)، مسألة استمثال، مسألة وعد الخ.
- نموذج التحسيب: النموذج الأكثر شيوعا للتحسيب هونموذج آلة تورنگ البترية، ولكن الكثير من أصناف التعقد ترتكز على آلة تورنگ غير البترية، الدارات المنطقية، آلة تورنگ الكمومية، دارات رتيبة.
- المورد (أوالموارد) المحدودة والحدود: عادة ما تدرج هاتين الخاصيتين معا، مثل "الزمن الكثيرحدودي"، "الفضاء اللوغاريتمي" ، "العمق الثابت"، الخ.
كما يمكن توصيف الكثير من أصناف التعقيد وفقاً للمنطق الرياضي اللازم للتعبير عنها، وانظر التعقيد الوصفي.
أصناف تعقيد مهمة
تعهد الكثير من أصناف التعقيد وفقاً للزمن أوالمكان الذي تستغرقه الخووارزمية. أبرز أصناف التعقيد لمسائل القرار تعهد وفق التالي:
| صنف التعقيد
|
نموذج التحسيب
|
قيود المورد
|
|
DTIME(f(n))
|
آلة تورنگ البترية
|
Time f(n)
|
|
P
|
آلة تورنگ البترية
|
Time poly(n)
|
|
EXPTIME
|
آلة تورنگ البترية
|
Time 2poly(n)
|
|
NTIME(f(n))
|
آلة تورنگ غير البترية
|
Time f(n)
|
|
NP
|
آلة تورنگ غير البترية
|
Time poly(n)
|
|
NEXPTIME
|
آلة تورنگ غير البترية
|
Time 2poly(n)
|
|
DSPACE(f(n))
|
آلة تورنگ البترية
|
Space f(n)
|
|
L
|
آلة تورنگ البترية
|
Space O(log n)
|
|
PSPACE
|
آلة تورنگ البترية
|
Space poly(n)
|
|
EXPSPACE
|
آلة تورنگ البترية
|
Space 2poly(n)
|
|
NSPACE(f(n))
|
آلة تورنگ غير البترية
|
Space f(n)
|
|
NL
|
آلة تورنگ غير البترية
|
Space O(log n)
|
|
NPSPACE
|
آلة تورنگ غير البترية
|
Space poly(n)
|
|
NEXPSPACE
|
آلة تورنگ غير البترية
|
Space 2poly(n)
|
وقد اتضح حتى PSPACE = NPSPACE and EXPSPACE = NEXPSPACE حسب مبرهنة ساڤيتش.
Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using boolean circuits and BQP and QMA, which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems.
العلاقات بين أصناف التعقيد
الجدول التالي يوضح بعض أصناف المشاكل (أواللغات أوالنحو) التي تؤخذ في الاعتبار في نظرية التعقيد. إذا كان الصنف X هومجموعة جزئية من y، فإن X توضع تحت Y وتوصلان بخط غامق، بينما يستخدم الخط المنقط للدلالة على عدم معهدتنا فيما إذا كانتا متساويتين أما لا. وتقنياً، فإن التجزئة إلى "قابل للبت" و"غير قابل للبت" يتعلق أكثر بدراسة نظرية الحسوبية إلا أنه مفيد لوضع أصناف التعقيد في المنظور.
|
|
|
|
|
|
| Type 0 (Recursively enumerable) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Type 1 (Context Sensitive) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
مبرهنات التراتب
الموضوعة الرئيسية: time hierarchy theorem and space hierarchy theorem
بشكل أكثر دقة، فإن مبرهنة التراتب الزمني تنص على
-
.
مبرهنة التراتب الفراغي تنص على
-
.
انظر أيضاً
مراجع
قراءة متقدمة
-
حديقة التعقيد: مرجع ضخم للخبراء يضم قائمة كبيرة من أصناف التعقيد.
-
مخطط من قبل نيل إيمرمان Neil Immerman يظهر هيكلية أصناف التعقيد وعلاقتها مع بعضها.
-
Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. يعد هذا الكتاب المرجع المعياري إذا پي التامة.
