قسم تعقيد

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

وفي هذا السياق، مجموعة المسائل التي يمكن حلها بواسطة موارد حيث أنَّ n هو طول المُدخل.

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

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

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

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

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

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