فئة التعقيد

هذه صفحة مكتوبة بالعربية البسيطة، انظر الصفحة الأصلية
سياق مختلف أصناف التعقيد.

في نظرية التعقيد التحسيبي ، صنف التعقيد 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. يعد هذا الكتاب المرجع المعياري إن بي التامة.
تمّ الاسترجاع من "https://www.marefa.org/صنف_تعقيد"