قسم تعقيد

في علم التعقيد الحسابي، قسم تعقيد هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين، اغلب الاقسام لديها التعريف التالي:

مجموعة المسائل التي يمكن حلها بواسطة $O(f(n))$ موارد حيث أنَّ n هو طول المُدخل.

على سبيل المثال: القسم NP هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي $O(n^c)$) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسم بيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي (أي انها تسخدم $O(n^c)$ مكان اضافي).

الاقسام الأساسية مُعرفة حسب المتغيرات التالية:

1. نوع المسألة الحسابية: على الاغلب المسائل هي مسائل تقرير (decision problem), ولكن اقسام التعقيد يمكن تعريفها أيضا بواسطة مسائل دوال (function problem) مثل القسم FP أو مسائل عد (counting problem) مثل P# أو مسائل استمثال...
2. نوع نموذج الحساب: على الاغلب نموذج الحساب هو آلة تيورنج الحتمية ولكن العديد من الاقسام تُعرف بالة تيورنج غير حتمية، دوائر بوليانية، آلة تيورنج كمومية...
3. المورد الذي يتم تحديده والحدود: مثل «وقت حدودي», «مكان حدودي», «وقت لوجارثمي», ...

بعض الاقسام يمكن تشخيصها بواسطة المنطق الرياضي اللازم لتعريفها.

بعض أهم الاقسام

يتم تعريف الاقسام وفقا لنوع المورد أو النموذج المُستخدم ونلحق هنا بعض أهم الاقسام المعروفة:

• $\text{L}=\text{DSPACE}[\text{log}(n)]$
• $\text{NL}=\text{NSPACE}[\text{log}(n)]$
• $\text{P}={\cup }_{k\ge 1}\text{DTIME}[n^k]$
• $\text{NP}={\cup }_{k\ge 1}\text{NTIME}[n^k]$
• $\text{PSPACE}={\cup }_{k\ge 1}\text{DSPACE}[n^k]$
• $\text{NPSPACE}={\cup }_{k\ge 1}\text{NSPACE}[n^k]$
• $\text{E}={\cup }_{k\ge 1}\text{DSPACE}[k^n]$
• $\text{NE}={\cup }_{k\ge 1}\text{NSPACE}[k^n]$
• $\text{EXP}={\cup }_{k\ge 1}\text{DSPACE}[2^{n^k}]$
• $\text{NEXP}={\cup }_{k\ge 1}\text{NSPACE}[2^{n^k}]$
• $\text{EXPSPACE}={\cup }_{k\ge 1}\text{DSPACE}[2^{n^k}]$
• $\text{NEXPSPACE}={\cup }_{k\ge 1}\text{NSPACE}[2^{n^k}]$

على الاغلب هنا أُستخدِم النموذج الحسابي: آلة تيورنج حتمية وغير حتمية.

اقسام أخرى مهمة من ضمنها: BPP , RP,ZPP وهذه الاقسام مُعرفة بواسطة آلة تيورنج احتمالية ; الاقسام AC,NC وهذه الاقسام مُعرفة بواسطة دوائر بوليانية ; BQP,QAM وهذه الاقسام مُعرفة بواسطة آلة تيورنج كمومية ; #P وهو قسم مسائل عد. اقسام مثل IP,AM مُعرفة بواسطة نظام براهين تفاعلي. ALL هو قسم كل المسائل.

انظر أيضًا

• نظرية التعقيد الحسابي.
• مسألة P=NP
• خوارزمية

استزادة

• The Complexity Zoo: قائمة كبيرة لكل الاقسام المعروفة.

مصادر

• Algorithms and Theory of Computation Handbook, Second Edition - 2 Volume Set (Chapman & Hall/CRC Applied Algorithms and Data Structures series), ISBN 1-58488-818-0