قسم تعقيد

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

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

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

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

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

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

• بوابة رياضيات
• بوابة علم الحاسوب