في علم التعقيد الحسابي , قسم تعقيد هي مجموعة من المسائل المُتعلقة بالاساس فيما بينها بمورد مُعين , اغلب الاقسام لديها التعريف التالي:
- مجموعة المسائل التي يمكن حلها بواسطة موارد حيث أنَّ n هو طول المُدخل .
على سبيل المثال : القسم NP هو مجموعة المسائل التي يمكن حلها بوقت حدودي ( أي ) بواسطة آلة تيورنج غير حتمية, مثال آخر هو القسم بيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي ( أي انها تسخدم مكان اضافي) .
الاقسام الأساسية مُعرفة حسب المتغيرات التالية :
- نوع المسألة الحسابية : على الاغلب المسائل هي مسائل تقرير (decision problem) , ولكن اقسام التعقيد يمكن تعريفها أيضا بواسطة مسائل دوال (function problem) مثل القسم FP أو مسائل عد (counting problem) مثل P# أو مسائل استمثال ...
- نوع نموذج الحساب : على الاغلب نموذج الحساب هو آلة تيورنج الحتمية ولكن العديد من الاقسام تُعرف بالة تيورنج غير حتمية , دوائر بوليانية , آلة تيورنج كمومية ...
- المورد الذي يتم تحديده والحدود : مثل "وقت حدودي" , "مكان حدودي" , "وقت لوجارثمي" , ...
بعض الاقسام يمكن تشخيصها بواسطة المنطق الرياضي اللازم لتعريفها .
بعض أهم الاقسام
يتم تعريف الاقسام وفقا لنوع المورد أو النموذج المُستخدم ونلحق هنا بعض أهم الاقسام المعروفة :
![{\displaystyle {\mbox{L}}={\mbox{DSPACE}}[{\mbox{log}}(n)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a05aa10d4859c5780404c0bfb79c096ddf2e51e)
![{\displaystyle {\mbox{NL}}={\mbox{NSPACE}}[{\mbox{log}}(n)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a7ba165636ed5dd3786d1676051455977a53baa)
![{\displaystyle {\mbox{P}}=\cup _{k\geq 1}{\mbox{DTIME}}[n^{k}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0125ab8e1f837f2f51a99c474582178704b00118)
![{\displaystyle {\mbox{NP}}=\cup _{k\geq 1}{\mbox{NTIME}}[n^{k}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4d7eef01671a2b9fd62424f57db576ca79e4ded)
![{\displaystyle {\mbox{PSPACE}}=\cup _{k\geq 1}{\mbox{DSPACE}}[n^{k}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/959a099e63c9707b52e4b6bd31f4e8a96dfa1e1a)
![{\displaystyle {\mbox{NPSPACE}}=\cup _{k\geq 1}{\mbox{NSPACE}}[n^{k}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c46632539e7a66f18d5b39c9765204a9cc721800)
![{\displaystyle {\mbox{E}}=\cup _{k\geq 1}{\mbox{DSPACE}}[k^{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3939c8b39fb1e35a412be8564a70a2c454a0714f)
![{\displaystyle {\mbox{NE}}=\cup _{k\geq 1}{\mbox{NSPACE}}[k^{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82b7f333f5adc01794bef49ff3ad1e48efa77381)
![{\displaystyle {\mbox{EXP}}=\cup _{k\geq 1}{\mbox{DSPACE}}[2^{n^{k}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a9abeb0fd4730dc9f518fe9650f477539c0afe0)
![{\displaystyle {\mbox{NEXP}}=\cup _{k\geq 1}{\mbox{NSPACE}}[2^{n^{k}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a79834b3ab4a180b2ca685d7440ef878fe53d322)
![{\displaystyle {\mbox{EXPSPACE}}=\cup _{k\geq 1}{\mbox{DSPACE}}[2^{n^{k}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edc06d2d817cff64ad803573d8dfa4ebc832f398)
![{\displaystyle {\mbox{NEXPSPACE}}=\cup _{k\geq 1}{\mbox{NSPACE}}[2^{n^{k}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0763f9dace8cdd5aad4ece7f749ffd3f94454eb)
على الاغلب هنا أُستخدِم النموذج الحسابي : آلة تيورنج حتمية وغير حتمية .
اقسام أخرى مهمة من ضمنها : BPP , RP,ZPP وهذه الاقسام مُعرفة بواسطة آلة تيورنج احتمالية ; الاقسام AC,NC وهذه الاقسام مُعرفة بواسطة دوائر بوليانية ; BQP,QAM وهذه الاقسام مُعرفة بواسطة آلة تيورنج كمومية ; #P وهو قسم مسائل عد . اقسام مثل IP,AM مُعرفة بواسطة نظام براهين تفاعلي . ALL هو قسم كل المسائل .
مقالات ذات صلة
استزادة
- The Complexity Zoo: قائمة كبيرة لكل الاقسام المعروفة .
مصادر
- Algorithms and Theory of Computation Handbook, Second Edition - 2 Volume Set (Chapman & Hall/CRC Applied Algorithms and Data Structures series) ,