قسم تعقيد

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