ماذا تعرف عن قسم تعقيد

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



مجموعة المسائل التي يمكن حلها بواسطة







O

(

f

(

n

)

)





{\displaystyle O(f(n))}



موارد حيث أنَّ n هو طول المُدخل.

على سبيل المثال: القسم NP هو مجموعة المسائل التي يمكن حلها بوقت حدودي (أي







O

(



n



c





)





{\displaystyle O(n^{c})}



) بواسطة آلة تيورنج غير حتمية، مثال آخر هو القسم بيسبايس وهو مجموعة المسائل التي يمكن حلها بواسطة آلة تيورنج حتمية وتستخدم مكان اضافي طوله حدودي (أي انها تسخدم







O

(



n



c





)





{\displaystyle O(n^{c})}



مكان اضافي).

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



نوع المسألة الحسابية: على الاغلب المسائل هي مسائل تقرير (decision problem), ولكن اقسام التعقيد يمكن تعريفها أيضا بواسطة مسائل دوال (function problem) مثل القسم FP أو مسائل عد (counting problem) مثل P# أو مسائل استمثال...

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

المورد الذي يتم تحديده والحدود: مثل «وقت حدودي», «مكان حدودي», «وقت لوجارثمي», ...

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