صنف تعقيد

هذا المقال يتضمن أسماءً أعجمية تتطلب حروفاً إضافية (پ چ ژ گ ڤ ڠ).
لمطالعة نسخة مبسطة، بدون حروف إضافية
سياق مختلف أصناف التعقيد.

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

مجموعة من المسائل التي يمكن حلها عن طريق آلة مجردة باستخدام [1] من مورد تحسيبي 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 وتوصلان بخط غامق، بينما يستخدم الخط المنقط للدلالة على عدم معرفتنا فيما إذا كانتا متساويتين أما لا. وتقنياً، فإن التجزئة إلى "قابل للبت" و"غير قابل للبت" يتعلق أكثر بدراسة نظرية الحسوبية إلا أنه مفيد لوضع أصناف التعقيد في المنظور.

مسألة قرار
SolidLine.png SolidLine.png
Type 0 (Recursively enumerable)
لا يمكن البت فيها
SolidLine.png
Decidable
SolidLine.png
EXPSPACE
DottedLine.png
NEXPTIME
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
Type 1 (Context Sensitive)
DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png
Co-NP
BQP
NP
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png DottedLine.png
BPP
DottedLine.png
SolidLine.png DottedLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png DottedLine.png
P
SolidLine.png DottedLine.png DottedLine.png
SolidLine.png
NC
SolidLine.png SolidLine.png
Type 2 (Context Free)
SolidLine.png
Type 3 (Regular)


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

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

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

.

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

.

انظر أيضاً

مراجع

قراءة متقدمة

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