صنف تعقيد

سياق مختلف أصناف التعقيد.

في نظرية التعقيد التحسيبي ، صنف التعقيد complexity class هي مجموعة من المسائل المتشابهة في تعقيد مواردها التحسيبية. ولكل صنف تعقيد تعريف من الشكل:

مجموعة من المسائل التي يمكن حلها عن طريق آلة مجردة باستخدام $O(f(n))\,$ من مورد تحسيبي R، حيث n هو حجم المدخلات.

على سبيل المثال ، يضم صنف إن پي مجموعة من مسائل القرار التي يمكن حلها من قبل آلة تورنگ لاقطعية في زمن كثير حدودي ، بينما يضم صنف 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)				لا يمكن البت فيها
Decidable
EXPSPACE
NEXPTIME
EXPTIME
PSPACE
Type 1 (Context Sensitive)
		Co-NP	BQP		NP
			BPP
		P
	NC
Type 2 (Context Free)
Type 3 (Regular)

 مبرهنات التراتب

المقالة الرئيسية: time hierarchy theorem and space hierarchy theorem

بشكل أكثر دقة، فإن مبرهنة التراتب الزمني تنص على

$\operatorname {DTIME} {\big (}f(n){\big )}\subsetneq \operatorname {DTIME} {\big (}f(n)\cdot \log ^{2}(f(n)){\big )}$.

مبرهنة التراتب الفراغي تنص على

$\operatorname {DSPACE} {\big (}f(n){\big )}\subsetneq \operatorname {DSPACE} {\big (}f(n)\cdot \log(f(n)){\big )}$.

 انظر أيضاً

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 قراءة متقدمة

• حديقة التعقيد: مرجع ضخم للخبراء يضم قائمة كبيرة من أصناف التعقيد.
• مخطط من قبل نيل إيمرمان 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. يعد هذا الكتاب المرجع المعياري إن پي التامة.