فئة التعقيد

تُعدّ مسائل القرار من أكثر المسائل شيوعًا في التحليل في علوم الحاسوب النظرية، وهي المسائل التي يمكن صياغتها على شكل أسئلة إجابتها "نعم" أو "لا" . فعلى سبيل المثال، يُعدّ مثال مسألة أولية الأعداد المذكور أعلاه مثالًا على مسألة قرار، إذ يمكن تمثيلها بالسؤال "هل هو عدد طبيعي ؟" الذي يُجيب عليه بنعم أو لا.${\displaystyle n}$العدد الأولي . من منظور نظرية الحوسبة، تُعرَّف مسألة القرار بأنها مجموعة سلاسل الإدخال التي سيجيب عليها الحاسوب الذي يُشغِّل خوارزمية صحيحة بـ "نعم". في مثال الأعداد الأولية،${\displaystyle {\texttt {PRIME}}}$هي مجموعة السلاسل النصية التي تمثل الأعداد الطبيعية، والتي عند إدخالها إلى جهاز كمبيوتر يُشغّل خوارزمية تختبر أولية الأعداد بشكل صحيح ، تُجيب الخوارزمية بـ "نعم، هذا العدد أولي". يُشار إلى هذا النمط "نعم-لا" غالبًا بصيغة "قبول-رفض"؛ أي أن الخوارزمية "تقبل" سلسلة الإدخال إذا كانت إجابة مسألة القرار "نعم"، و"ترفضها" إذا كانت الإجابة "لا".

على الرغم من أن بعض المشكلات لا يمكن التعبير عنها بسهولة كمشكلات قرار، إلا أنها تشمل نطاقًا واسعًا من المشكلات الحسابية. ^{[ 2 ]} تشمل أنواع المشكلات الأخرى التي تُعرَّف فئات التعقيد المحددة على أساسها ما يلي:

• مشاكل الدوال (مثل FP )
• مسائل العد (مثل مسائل العد )
• مشاكل التحسين
• مشاكل الوعود (انظر القسم "أنواع أخرى من المشاكل")

آلة تورينج هي نموذج رياضي لآلة حاسوبية عامة. وهي النموذج الأكثر استخدامًا في نظرية التعقيد، ويعود ذلك في جزء كبير منه إلى الاعتقاد بأنها تتمتع بنفس قوة أي نموذج حاسوبي آخر، وسهولة تحليلها رياضيًا. والأهم من ذلك، يُعتقد أنه إذا وُجدت خوارزمية تحل مشكلة معينة، فإنه توجد أيضًا آلة تورينج تحل نفس المشكلة (وهذا ما يُعرف بنظرية تشرش-تورينج )؛ أي أنه يُعتقد أن كل خوارزمية يمكن تمثيلها كآلة تورينج.

ميكانيكيًا، تعالج آلة تورينج الرموز (التي تقتصر عادةً على البتات 0 و1 لتوفير ربط بديهي بأجهزة الكمبيوتر في الحياة الواقعية) الموجودة على شريط طويل جدًا. تستطيع آلة تورينج القراءة والكتابة، رمزًا تلو الآخر، باستخدام رأس قراءة الشريط. يتم تحديد طريقة عملها بالكامل من خلال مجموعة محدودة من التعليمات الأساسية، مثل: "في الحالة 42، إذا كان الرمز المرئي هو 0، فاكتب 1؛ إذا كان الرمز المرئي هو 1، فانتقل إلى الحالة 17؛ في الحالة 17، إذا كان الرمز المرئي هو 0، فاكتب 1 وانتقل إلى الحالة 6". تبدأ آلة تورينج بسلسلة الإدخال فقط على شريطها، وتكون بقية المساحة فارغة. تقبل آلة تورينج الإدخال إذا دخلت حالة قبول محددة، وترفضه إذا دخلت حالة رفض. تُعد آلة تورينج الحتمية أبسط أنواع آلات تورينج، حيث تستخدم مجموعة ثابتة من القواعد لتحديد إجراءاتها المستقبلية (ولهذا السبب تُسمى " حتمية ").

يمكن تعريف المسألة الحسابية من منظور آلة تورينج على أنها مجموعة سلاسل الإدخال التي تقبلها آلة تورينج معينة. على سبيل المثال، مسألة الأعداد الأولية${\displaystyle {\texttt {PRIME}}}$من الأعلى، تمثل مجموعة السلاسل (التي تمثل الأعداد الطبيعية) التي تقبلها آلة تورينج عند تشغيل خوارزمية تختبر أولية الأعداد بشكل صحيح . يُقال إن آلة تورينج تتعرف على لغة ما (تذكر أن مصطلحي "المشكلة" و"اللغة" مترادفان إلى حد كبير في نظرية الحوسبة والتعقيد) إذا قبلت جميع المدخلات التي تنتمي إلى تلك اللغة، ويُقال إنها تُقرر لغة ما إذا رفضت بالإضافة إلى ذلك جميع المدخلات التي لا تنتمي إليها (قد تتسبب بعض المدخلات في استمرار عمل آلة تورينج إلى ما لا نهاية، لذا فإن قابلية الحسم تفرض قيدًا إضافيًا على قابلية التعرف، وهو أن تتوقف آلة تورينج عند جميع المدخلات). آلة تورينج التي "تحل" مشكلة ما، يُقصد بها عمومًا تلك التي تُقرر اللغة.

تُتيح آلات تورينج مفاهيم بديهية عن "الزمن" و"المكان". يُعرَّف التعقيد الزمني لآلة تورينج على مُدخل مُحدد بأنه عدد الخطوات الأولية التي تتخذها الآلة للوصول إلى حالة القبول أو الرفض. أما التعقيد المكاني ، فيُعرَّف بأنه عدد الخلايا الموجودة على شريطها والتي تستخدمها للوصول إلى حالة القبول أو الرفض.

آلة تورينغ الحتمية (DTM) هي نوع من آلة تورينغ غير الحتمية (NTM). ببساطة، آلة تورينغ غير الحتمية هي آلة تورينغ عادية تتميز بقدرتها على استكشاف عدة مسارات مستقبلية محتملة انطلاقًا من حالة معينة، و"اختيار" فرع يقبل المدخلات (إن وُجد). أي أنه بينما تتبع آلة تورينغ الحتمية مسارًا حسابيًا واحدًا فقط، يمكن تخيل آلة تورينغ غير الحتمية كشجرة حسابية تتفرع إلى مسارات حسابية متعددة في كل خطوة (انظر الصورة). إذا توقف فرع واحد على الأقل من الشجرة عند شرط "القبول"، فإن آلة تورينغ غير الحتمية تقبل المدخلات. وبهذه الطريقة، يمكن اعتبار آلة تورينغ غير الحتمية وكأنها تستكشف جميع الاحتمالات الحسابية بالتوازي وتختار فرعًا يقبل المدخلات. ^{[ 3 ]} لا يُقصد بآلات تورينغ غير الحتمية أن تكون نماذج قابلة للتنفيذ فيزيائيًا، بل هي ببساطة آلات مجردة ذات أهمية نظرية تُنتج عددًا من فئات التعقيد المهمة (والتي غالبًا ما يكون لها تعريفات مكافئة قابلة للتنفيذ فيزيائيًا).

يُعرَّف التعقيد الزمني لآلة تورينج غير الخطية بأنه الحد الأقصى لعدد الخطوات التي تستخدمها الآلة في أي فرع من فروع حسابها. ^{[ 4 ]} وبالمثل، يُعرَّف التعقيد المكاني لآلة تورينج غير الخطية بأنه الحد الأقصى لعدد الخلايا التي تستخدمها الآلة في أي فرع من فروع حسابها.

يمكن اعتبار آلات تورينج المنفصلة (DTMs) حالة خاصة من آلات تورينج غير الحتمية (NTMs) التي لا تستفيد من خاصية عدم الحتمية. وبالتالي، فإن أي عملية حسابية يمكن إجراؤها بواسطة آلة تورينج منفصلة يمكن إجراؤها أيضًا بواسطة آلة تورينج غير حتمية مكافئة. كما يمكن محاكاة أي آلة تورينج غير حتمية باستخدام آلة تورينج منفصلة (حيث ستقوم آلة التورينج المنفصلة ببساطة بحساب كل فرع حسابي ممكن على حدة). ومن ثم، فإنهما متكافئتان من حيث قابلية الحساب. مع ذلك، غالبًا ما تتطلب محاكاة آلة تورينج غير حتمية باستخدام آلة تورينج منفصلة وقتًا و/أو موارد ذاكرة أكبر؛ وكما سيتبين، فإن مدى أهمية هذا التباطؤ بالنسبة لأنواع معينة من المسائل الحسابية يُعد سؤالًا مهمًا في نظرية التعقيد الحسابي.

التعقيد الزمني لخوارزمية ما بالنسبة لنموذج آلة تورينج هو عدد الخطوات التي تستغرقها آلة تورينج لتشغيل خوارزمية على حجم إدخال معين. وبصورة رسمية، فإن التعقيد الزمني لخوارزمية مُنفذة باستخدام آلة تورينج هو${\displaystyle M}$تُعرَّف بأنها الدالة${\displaystyle t_{M}:\mathbb {N} \to \mathbb {N} }$، أين${\displaystyle t_{M}(n)}$هو الحد الأقصى لعدد الخطوات التي${\displaystyle M}$يستقبل أي مدخلات ذات طول${\displaystyle n}$.

في نظرية التعقيد الحسابي، لا يهتم علماء الحاسوب النظريون بقيم وقت التشغيل المحددة بقدر اهتمامهم بالفئة العامة للدوال التي تندرج ضمنها دالة التعقيد الزمني. على سبيل المثال، هل دالة التعقيد الزمني دالة متعددة الحدود ؟ أم دالة لوغاريتمية ؟ أم دالة أسية ؟ أم نوع آخر من الدوال؟

يُعرَّف التعقيد المكاني للخوارزمية بالنسبة لنموذج آلة تورينج بأنه عدد الخلايا الموجودة على شريط آلة تورينج اللازمة لتشغيل الخوارزمية على حجم إدخال مُحدد. وبصورة رسمية، فإن التعقيد المكاني للخوارزمية المُنفذة باستخدام آلة تورينج هو${\displaystyle M}$تُعرَّف بأنها الدالة${\displaystyle s_{M}:\mathbb {N} \to \mathbb {N} }$، أين${\displaystyle s_{M}(n)}$هو الحد الأقصى لعدد الخلايا التي${\displaystyle M}$يستخدم على أي مدخلات ذات طول${\displaystyle n}$.

P هي فئة المسائل التي يمكن حلها بواسطة آلة تورينغ حتمية في وقت متعدد الحدود ، و NP هي فئة المسائل التي يمكن حلها بواسطة آلة تورينغ غير حتمية في وقت متعدد الحدود. أو بصورة أكثر دقة،

${\displaystyle {\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})}$

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})}$

غالباً ما يقال إن P هي فئة المشاكل التي يمكن حلها "بسرعة" أو "بكفاءة" بواسطة جهاز كمبيوتر حتمي، لأن التعقيد الزمني لحل مشكلة في P يزداد ببطء نسبيًا مع حجم المدخلات.

من الخصائص المهمة لفئة NP أنه يمكن تعريفها بشكل مكافئ على أنها فئة المسائل التي يمكن التحقق من حلولها بواسطة آلة تورينغ حتمية في وقت متعدد الحدود. أي أن اللغة تنتمي إلى فئة NP إذا وُجدت آلة تورينغ حتمية تعمل في وقت متعدد الحدود، تُسمى المُدقِّق، تأخذ سلسلة نصية كمدخل.${\displaystyle w}$وسلسلة شهادة بحجم متعدد الحدود${\displaystyle c}$ويقبل${\displaystyle w}$لو${\displaystyle w}$موجود في اللغة ويرفض${\displaystyle w}$لو${\displaystyle w}$غير موجود في اللغة. وبشكل بديهي، تعمل الشهادة كدليل على أن المدخلات${\displaystyle w}$موجود في اللغة. رسميًا: ^{[ 5 ]}

NP هي فئة اللغات${\displaystyle L}$والتي يوجد لها آلة تورينغ حتمية ذات زمن متعدد الحدود${\displaystyle M}$ومتعددة الحدود${\displaystyle p}$بحيث يكون ذلك لجميع${\displaystyle w\in \{0,1\}^{*}}$،${\displaystyle w}$هو في${\displaystyle L}$إذا وفقط إذا كان هناك شيء ما${\displaystyle c\in \{0,1\}^{p(|w|)}}$بحيث${\displaystyle M(w,c)}$يقبل.

يُبرز هذا التكافؤ بين التعريف غير الحتمي وتعريف المُدقِّق صلةً جوهريةً بين عدم الحتمية وقابلية التحقق من الحل. علاوةً على ذلك، فإنه يُوفِّر طريقةً مفيدةً لإثبات أن لغةً ما تنتمي إلى فئة NP ، وذلك ببساطة عن طريق تحديد شهادة مناسبة وإثبات إمكانية التحقق منها في وقت متعدد الحدود.

EXPTIME (يُختصر أحيانًا إلى EXP ) هي فئة مسائل القرار التي يمكن حلها بواسطة آلة تورينغ حتمية في وقت أسي، و NEXPTIME (يُختصر أحيانًا إلى NEXP ) هي فئة مسائل القرار التي يمكن حلها بواسطة آلة تورينغ غير حتمية في وقت أسي. أو بصورة أكثر دقة،

${\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(2^{n^{k}})}$

${\displaystyle {\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

تُعتبر مجموعة EXPTIME مجموعة شاملة تمامًا من P ، وتُعتبر مجموعة NEXPTIME مجموعة شاملة تمامًا من NP . كما أن مجموعة EXPTIME${\displaystyle \subseteq }$NEXPTIME . ليس من المعروف ما إذا كان هذا صحيحًا، ولكن إذا كان P = NP، فيجب أن يكون EXPTIME مساويًا لـ NEXPTIME .

على الرغم من إمكانية تعريف فئات تعقيد زمني لوغاريتمي ، إلا أن هذه الفئات ضيقة للغاية، إذ أن الأوقات شبه الخطية لا تُمكّن حتى آلة تورينج من قراءة المدخلات بالكامل (لأن${\displaystyle \log n<n}$^{[ أ ] [ 9 ]} مع ذلك ، يوجد عددٌ كبيرٌ من المسائل التي يُمكن حلّها في فضاء لوغاريتمي. تتطلب تعريفات هذه الفئات آلة تورينغ ثنائية الشريط، بحيث يُمكن للآلة تخزين المدخلات كاملةً (يمكن إثبات أن آلة تورينغ ثنائية الشريط تُكافئ آلة تورينغ أحادية الشريط من حيث قابلية الحساب ). ^{[ 10 ]} في نموذج آلة تورينغ ثنائية الشريط، يكون أحد الشريطين هو شريط الإدخال، وهو للقراءة فقط. أما الآخر فهو شريط العمل، الذي يسمح بالقراءة والكتابة، وهو الشريط الذي تُجري عليه آلة تورينغ العمليات الحسابية. يُقاس تعقيد المساحة لآلة تورينغ بعدد الخلايا المُستخدمة على شريط العمل.

يُعرَّف L (ويُشار إليه أحيانًا بـ LOGSPACE ) بأنه فئة المسائل القابلة للحل في الفضاء اللوغاريتمي على آلة تورينغ حتمية، بينما يُعرَّف NL (ويُشار إليه أحيانًا بـ NLOGSPACE ) بأنه فئة المسائل القابلة للحل في الفضاء اللوغاريتمي على آلة تورينغ غير حتمية. أو بصورة أكثر دقة، ^{[ 10 ]}

${\displaystyle {\mathsf {L}}={\mathsf {DSPACE}}(\log n)}$

${\displaystyle {\mathsf {NL}}={\mathsf {NSPACE}}(\log n)}$

من المعروف أن${\displaystyle {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {P}}}$ومع ذلك، فإنه من غير المعروف ما إذا كانت أي من هذه العلاقات مناسبة أم لا.

تُعدّ فئتا التعقيد PSPACE و NPSPACE نظيرتين مكانيتين للفئتين P و NP . أي أن PSPACE هي فئة المسائل القابلة للحل في فضاء متعدد الحدود بواسطة آلة تورينغ حتمية، بينما NPSPACE هي فئة المسائل القابلة للحل في فضاء متعدد الحدود بواسطة آلة تورينغ غير حتمية. بتعبير أدق،

${\displaystyle {\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$

${\displaystyle {\mathsf {NPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}$

على الرغم من أنه ليس من المعروف ما إذا كانت P = NP ، فقد أثبتت نظرية سافيتش الشهيرة أن PSPACE = NPSPACE . ومن المعروف أيضًا أن${\displaystyle {\mathsf {P}}\subseteq {\mathsf {PSPACE}}}$وهذا ما يستنتج بديهيًا من حقيقة أن الكتابة إلى خلية على شريط آلة تورينج تستغرق وحدة زمنية واحدة، وبالتالي فإن آلة تورينج التي تعمل في زمن متعدد الحدود لا يمكنها الكتابة إلا إلى عدد متعدد الحدود من الخلايا. ويُشتبه في أن P أصغر من PSPACE ، لكن هذا لم يُثبت بعد.

تُعدّ فئتا التعقيد EXPSPACE و NEXPSPACE نظيرتين مكانيتين لفئتي EXPTIME و NEXPTIME . أي أن EXPSPACE هي فئة المسائل التي يمكن حلها في فضاء أسي بواسطة آلة تورينغ حتمية، بينما NEXPSPACE هي فئة المسائل التي يمكن حلها في فضاء أسي بواسطة آلة تورينغ غير حتمية. أو بصورة أكثر دقة،

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

${\displaystyle {\mathsf {NEXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}$

أثبتت نظرية سافيتش أن EXPSPACE = NEXPSPACE . هذه الفئة واسعة للغاية: من المعروف أنها مجموعة شاملة صارمة لـ PSPACE و NP و P ، ويُعتقد أنها مجموعة شاملة صارمة لـ EXPTIME .

تُحفز عمليات الاختزال مفهوم صعوبة المسألة بالنسبة لفئة تعقيد معينة.${\displaystyle X}$يُعدّ الأمر صعبًا بالنسبة لفئة من المسائل C إذا كان بالإمكان اختزال كل مسألة في C في زمن متعدد الحدود إلى${\displaystyle X}$وبالتالي، لا توجد مشكلة في لغة C أصعب من${\displaystyle X}$، حيث أن خوارزمية لـ${\displaystyle X}$يُتيح لنا ذلك حلّ أي مسألة في لغة C بتباطؤ لا يتجاوز كثير الحدود. ومن الأهمية بمكان أن مجموعة المسائل الصعبة بالنسبة لفئة NP تُسمى مجموعة المسائل الصعبة من فئة NP .

إذا كانت هناك مشكلة${\displaystyle X}$إذا كان الأمر صعبًا بالنسبة للغة C وهو موجود أيضًا في لغة C ، فـ${\displaystyle X}$يُقال إنها كاملة بالنسبة لـ C. وهذا يعني أن${\displaystyle X}$تُعدّ هذه المسألة أصعب مسألة في لغة C (حيث يمكن أن تكون هناك العديد من المسائل التي تتساوى في الصعوبة، بتعبير أدق).${\displaystyle X}$هي صعبة مثل أصعب المسائل في لغة C ).

تُعدّ فئة مسائل NP- الكاملة ذات أهمية خاصة ، وهي أصعب المسائل في فئة NP . ولأن جميع مسائل NP يُمكن اختزالها في زمن متعدد الحدود إلى مسائل NP- كاملة، فإن إيجاد مسألة NP- كاملة يُمكن حلّها في زمن متعدد الحدود يعني أن P  = NP . 

الفئات الأساسية لتعقيد الوقت العشوائي هي ZPP و RP و co-RP و BPP و PP .

الفئة الأكثر صرامة هي ZPP (الوقت متعدد الحدود الاحتمالي بدون خطأ)، وهي فئة من المشكلات التي يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينج الاحتمالية باحتمال خطأ 0. بشكل بديهي، هذه هي الفئة الأكثر صرامة من المشكلات الاحتمالية لأنها لا تتطلب أي خطأ على الإطلاق .

هناك فئة أكثر مرونة قليلاً تُسمى RP (زمن متعدد الحدود العشوائي)، والتي لا تُبقي على أي خطأ للسلاسل غير الموجودة في اللغة، ولكنها تسمح بخطأ محدود للسلاسل الموجودة في اللغة. وبشكل أكثر دقة، تُصنف اللغة ضمن فئة RP إذا وُجدت آلة تورينغ احتمالية ذات زمن متعدد الحدود.${\displaystyle M}$بحيث إذا لم تكن السلسلة موجودة في اللغة،${\displaystyle M}$يتم رفضها دائمًا، وإذا كانت السلسلة موجودة في اللغة...${\displaystyle M}$يقبل باحتمالية لا تقل عن 1/2. تُعرَّف فئة co-RP بشكل مشابه، باستثناء أن الأدوار معكوسة: لا يُسمح بالخطأ للسلاسل النصية في اللغة، ولكن يُسمح به للسلاسل النصية خارجها. وبذلك، تشمل فئتا RP و co-RP جميع المشكلات التي يمكن حلها بواسطة آلات تورينغ الاحتمالية ذات الخطأ أحادي الجانب .

يؤدي تخفيف شروط الخطأ للسماح بالخطأ ثنائي الجانب إلى ظهور فئة BPP (الوقت متعدد الحدود الاحتمالي ذو الخطأ المحدود)، وهي فئة المسائل التي يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينغ احتمالية باحتمالية خطأ أقل من 1/3 (لكلا السلسلتين في اللغة وخارجها). تُعدّ BPP الأكثر أهمية من الناحية العملية بين فئات التعقيد الاحتمالي، إذ تتميز مسائلها بخوارزميات عشوائية فعّالة يمكن تشغيلها بسرعة على أجهزة الكمبيوتر الحقيقية. كما تُمثّل BPP محورًا لمسألة مهمة لم تُحل بعد في علوم الحاسوب، وهي ما إذا كان P=BPP ، وإذا صحّ ذلك، فسيعني أن العشوائية لا تزيد من القدرة الحسابية لأجهزة الكمبيوتر، أي أنه يمكن محاكاة أي آلة تورينغ احتمالية بواسطة آلة تورينغ حتمية مع تباطؤ لا يتجاوز الوقت متعدد الحدود.

أوسع فئة من المشكلات الاحتمالية التي يمكن حلها بكفاءة هي PP (الوقت متعدد الحدود الاحتمالي)، وهي مجموعة اللغات التي يمكن حلها بواسطة آلة تورينج الاحتمالية في وقت متعدد الحدود مع احتمال خطأ أقل من 1/2 لجميع السلاسل.

ZPP و RP و co-RP جميعها مجموعات جزئية من BPP ، والتي بدورها مجموعة جزئية من PP . والسبب في ذلك بديهي: فالفئات التي تسمح بخطأ صفري وخطأ أحادي الجانب فقط تقع جميعها ضمن الفئة التي تسمح بخطأ ثنائي الجانب، و PP ببساطة تُخفف من احتمالية الخطأ في BPP . وترتبط ZPP بـ RP و co-RP على النحو التالي:${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$أي أن ZPP تتكون تحديدًا من تلك المشكلات الموجودة في كل من RP و co-RP . وهذا بديهي، إذ أن RP و co-RP لا تسمحان إلا بالخطأ من جانب واحد: فـ co-RP لا تسمح بالخطأ في السلاسل النصية الموجودة في اللغة، و RP لا تسمح بالخطأ في السلاسل النصية غير الموجودة في اللغة. وبالتالي، إذا كانت المشكلة موجودة في كل من RP و co-RP ، فلا بد من عدم وجود خطأ في السلاسل النصية الموجودة في اللغة وغير الموجودة فيها (أي لا يوجد خطأ على الإطلاق)، وهذا هو تعريف ZPP تحديدًا .

تشمل فئات تعقيد الفضاء العشوائي المهمة BPL و RL و RLP .

تُعدّ فئة NP نظام إثبات بسيطًا، حيث يقتصر المُدقِّق على كونه آلة تورينغ حتمية تعمل في زمن متعدد الحدود ، وتقتصر العملية على جولة واحدة (أي أن المُثبت يُرسل برهانًا واحدًا كاملًا فقط - يُشار إليه عادةً بالشهادة - إلى المُدقِّق). بعبارة أخرى، في تعريف فئة NP (مجموعة مسائل القرار التي تكون فيها براهين حالات المسألة، عندما تكون الإجابة "نعم"، قابلة للتحقق في زمن متعدد الحدود بواسطة آلة تورينغ حتمية)، يُعدّ نظام إثبات يُبنى فيه البرهان بواسطة مُثبت غير مُحدد، وتكون آلة تورينغ الحتمية هي المُدقِّق. لهذا السبب، يُمكن أيضًا تسمية NP بـ dIP (الإثبات التفاعلي الحتمي)، على الرغم من ندرة استخدام هذا المصطلح.

اتضح أن فئة NP تستوعب كامل إمكانيات أنظمة الإثبات التفاعلية ذات المدققين الحتميين (ذوي الزمن متعدد الحدود)، إذ يمكن إثبات أنه في أي نظام إثبات ذي مدقق حتمي، لا يلزم أبدًا أكثر من جولة واحدة من المراسلة بين المُثبت والمدقق. وبالتالي، تتطلب أنظمة الإثبات التفاعلية، التي توفر قدرة حسابية أكبر من فئات التعقيد القياسية، مدققين احتماليين ، ما يعني أن أسئلة المدقق للمُثبت تُحسب باستخدام خوارزميات احتمالية . وكما ذُكر في القسم السابق حول الحساب العشوائي ، تُدخل الخوارزميات الاحتمالية خطأً في النظام، لذا تُعرَّف فئات التعقيد القائمة على أنظمة الإثبات الاحتمالية بدلالة احتمال الخطأ.${\displaystyle \epsilon }$.

إن فئة التعقيد الأكثر عمومية التي تنشأ من هذا التوصيف هي فئة IP (الوقت التفاعلي متعدد الحدود)، وهي فئة جميع المشكلات التي يمكن حلها بواسطة نظام إثبات تفاعلي${\displaystyle (P,V)}$، أين${\displaystyle V}$هو نظام احتمالي متعدد الحدود، ويحقق نظام البرهان خاصيتين: بالنسبة للغة${\displaystyle L\in {\mathsf {IP}}}$

1. (الكمال) سلسلة${\displaystyle w}$في${\displaystyle L}$يشير إلى${\displaystyle \Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\geq {\tfrac {2}{3}}}$
2. (سلامة) وتر${\displaystyle w}$ليس في${\displaystyle L}$يشير إلى${\displaystyle \Pr[V{\text{ accepts }}w{\text{ after interacting with }}P]\leq {\tfrac {1}{3}}}$

من السمات المهمة لـ IP أنها تساوي PSPACE . بعبارة أخرى، أي مشكلة يمكن حلها بواسطة نظام إثبات تفاعلي ذي وقت متعدد الحدود يمكن حلها أيضًا بواسطة آلة تورينج حتمية ذات موارد مساحة متعددة الحدود، والعكس صحيح.

يُنتج تعديل بروتوكول IP فئة تعقيد مهمة أخرى: بروتوكول آرثر-ميرلين ( AM ). في تعريف أنظمة الإثبات التفاعلية المستخدمة في IP ، لم يكن بإمكان المُثبت رؤية العملات التي يستخدمها المُدقِّق في حساباته الاحتمالية، بل كان بإمكانه فقط رؤية الرسائل التي يُنتجها المُدقِّق باستخدام هذه العملات. ولهذا السبب، تُسمى هذه العملات بالعملات العشوائية الخاصة . يمكن تقييد نظام الإثبات التفاعلي بحيث تكون العملات التي يستخدمها المُدقِّق عملات عشوائية عامة ؛ أي أن المُثبت قادر على رؤية هذه العملات. رسميًا، يُعرَّف بروتوكول آرثر -ميرلين (AM) بأنه فئة اللغات ذات الإثبات التفاعلي، حيث يُرسل المُدقِّق سلسلة عشوائية إلى المُثبت، فيرد المُثبت برسالة، ثم يقبل المُدقِّق الرسالة أو يرفضها بتطبيق دالة حتمية متعددة الحدود عليها. يمكن تعميم بروتوكول آرثر-ميرلين ( AM) إلى AM [ k ]، حيث k هو عدد الرسائل المتبادلة (وبالتالي، في الصيغة المُعمَّمة، يكون بروتوكول آرثر-ميرلين (AM) القياسي المُعرَّف أعلاه هو AM [2]). لكن هذا هو الحال بالنسبة للجميع${\displaystyle k\geq 2}$، AM [ k ]= AM [2]. وينطبق الأمر نفسه على ذلك.${\displaystyle {\mathsf {AM}}[k]\subseteq {\mathsf {IP}}[k]}$.

تشمل فئات التعقيد الأخرى المحددة باستخدام أنظمة الإثبات التفاعلية MIP (وقت متعدد الحدود التفاعلي متعدد المثبتين) و QIP (وقت متعدد الحدود التفاعلي الكمي).

فئة التعقيد P/poly هي مجموعة اللغات التي يمكن تقريرها بواسطة عائلات دوائر ذات حجم متعدد الحدود. يتضح وجود علاقة طبيعية بين تعقيد الدوائر وتعقيد الوقت. بشكل بديهي، اللغة ذات تعقيد الوقت المنخفض (أي التي تتطلب عددًا قليلًا نسبيًا من العمليات المتسلسلة على آلة تورينج) تتميز أيضًا بتعقيد دوائر منخفض (أي التي تتطلب عددًا قليلًا نسبيًا من العمليات المنطقية). رسميًا، يمكن إثبات أنه إذا كانت اللغة في${\displaystyle {\mathsf {DTIME}}(t(n))}$، أين${\displaystyle t}$هي دالة${\displaystyle t:\mathbb {N} \to \mathbb {N} }$إذن، فإن تعقيد الدائرة الكهربائية له${\displaystyle O(t^{2}(n))}$[ ^{16 ]} ويترتب على هذه الحقيقة مباشرة ^أن${\displaystyle {\mathsf {\color {Blue}P}}\subset {\textsf {P/poly}}}$بمعنى آخر، أي مشكلة يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينج حتمية يمكن حلها أيضًا بواسطة عائلة دوائر ذات حجم متعدد الحدود. ويتحقق ذلك أيضًا إذا كان التضمين صحيحًا، أي${\displaystyle {\textsf {P}}\subsetneq {\textsf {P/poly}}}$(على سبيل المثال، هناك بعض المشاكل غير القابلة للحل التي تقع في P/poly ).

تتمتع فئة P/poly بعدد من الخصائص التي تجعلها مفيدة للغاية في دراسة العلاقات بين فئات التعقيد. وعلى وجه الخصوص، فهي مفيدة في دراسة المشكلات المتعلقة بـ P مقابل NP . على سبيل المثال، إذا كانت هناك أي لغة في فئة NP وليست في فئة P/poly ، فإن${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}}$^{[ 17 ]} يُعدّ P/poly مفيدًا أيضًا في دراسة خصائص التسلسل الهرمي متعدد الحدود . على سبيل المثال، إذا كان NP ⊆ P /poly ، فإن PH ينهار إلى${\displaystyle \Sigma _{2}^{\mathsf {P}}}$يتوفر وصف كامل للعلاقات بين فئة P/poly وفئات التعقيد الأخرى في قسم " أهمية P/poly ". كما تُعدّ P/poly مفيدة في الدراسة العامة لخصائص آلات تورينج ، حيث يمكن تعريف هذه الفئة بشكل مكافئ على أنها فئة اللغات التي تتعرف عليها آلة تورينج ذات زمن متعدد الحدود ودالة توجيه محدودة متعددة الحدود .

هناك فئتان فرعيتان من P/poly تتميزان بخصائص فريدة، وهما NC و AC . تُعرَّف هاتان الفئتان ليس فقط من حيث حجم الدائرة، بل أيضًا من حيث عمقها . عمق الدائرة هو طول أطول مسار موجه من عقدة الإدخال إلى عقدة الإخراج. تُعرَّف الفئة NC بأنها مجموعة اللغات التي يمكن حلها بواسطة عائلات دوائر لا تقتصر على الحجم متعدد الحدود فحسب، بل على العمق متعدد اللوغاريتمات أيضًا. تُعرَّف الفئة AC بشكل مشابه للفئة NC ، إلا أنه يُسمح للبوابات المنطقية بعدد غير محدود من المدخلات (أي يمكن تطبيق بوابتي AND و OR على أكثر من بتين). تُعد الفئة NC فئةً بارزةً لأنها تُعرَّف بشكل مكافئ بأنها فئة اللغات التي تمتلك خوارزميات متوازية فعالة .

تُعدّ مسألة #P (تُنطق "شارب بي") فئةً مهمةً من مسائل العدّ، ويمكن اعتبارها النسخة العددية من مسألة NP . ^{[ 22 ]} وينشأ الارتباط بمسألة NP من حقيقة أن عدد حلول المسألة يساوي عدد الفروع المقبولة في شجرة حساب آلة تورينغ غير الحتمية . وبالتالي، تُعرَّف مسألة #P رسميًا على النحو التالي:

#P هي مجموعة جميع الدوال${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$بحيث توجد آلة تورينغ غير حتمية ذات زمن متعدد الحدود${\displaystyle M}$بحيث يكون ذلك لجميع${\displaystyle w\in \{0,1\}^{*}}$،${\displaystyle f(w)}$يساوي عدد الفروع المقبولة في${\displaystyle M}$شجرة الحساب الخاصة بـ${\displaystyle w}$[ ^{22 ]​}

وكما يمكن تعريف فئة NP من حيث عدم الحتمية ومن حيث المُدقِّق (أي كنظام إثبات تفاعلي )، كذلك يمكن تعريف فئة #P بشكل مكافئ من حيث المُدقِّق. تذكر أن مسألة القرار تنتمي إلى فئة NP إذا وُجدت شهادة قابلة للتحقق في زمن متعدد الحدود لحالة معينة من المسألة - أي أن فئة NP تسأل عما إذا كان هناك برهان عضوية (شهادة) للمدخل يمكن التحقق من صحته في زمن متعدد الحدود. تسأل الفئة #P عن عدد هذه الشهادات الموجودة. ^{[ 22 ]} في هذا السياق، تُعرَّف فئة #P على النحو التالي:

#P هي مجموعة الدوال${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$بحيث يوجد كثير حدود${\displaystyle p:\mathbb {N} \to \mathbb {N} }$وآلة تورينج ذات زمن متعدد الحدود${\displaystyle V}$(المُدقِّق)، بحيث يكون لكل${\displaystyle w\in \{0,1\}^{*}}$،${\displaystyle f(w)={\Big |}{\big \{}c\in \{0,1\}^{p(|w|)}:V(w,c)=1{\big \}}{\Big |}}$^{[ 23 ]} بعبارة أخرى ،${\displaystyle f(w)}$يساوي حجم المجموعة التي تحتوي على جميع الشهادات ذات الحجم متعدد الحدود لـ${\displaystyle w}$.

تُعدّ فئة FP فئةً مهمةً في تعقيد الدوال ، وهي فئة الدوال القابلة للحل بكفاءة. ^{[ 23 ]} وبشكلٍ أدق، تُمثّل FP مجموعة مسائل الدوال التي يُمكن حلّها بواسطة آلة تورينغ حتمية في وقتٍ متعدد الحدود . ^{[ 23 ]} يُمكن اعتبار FP مُكافئًا لمسألة الدوال P. ومن المهمّ أن FP تُقدّم بعض الأفكار حول مسائل العدّ، بالإضافة إلى المقارنة بين P و NP . إذا كان عدد مسائل P يساوي FP ، فإنّ الدوال التي تُحدّد عدد الشهادات لمسائل NP تكون قابلةً للحل بكفاءة. وبما أنّ حساب عدد الشهادات لا يقلّ صعوبةً عن تحديد وجود الشهادة من عدمه، فلا بدّ من أن يترتّب على ذلك أنّه إذا كان عدد مسائل P يساوي FP ، فإنّ P يساوي NP (مع العلم أنّه ليس من المعروف ما إذا كان هذا صحيحًا في الاتجاه المعاكس، أي ما إذا كان P يساوي NP يستلزم عدد مسائل P يساوي FP ). ^{[ 23 ]}

كما أن FP هي مسألة الدوال المكافئة لـ P ، فإن FNP هي مسألة الدوال المكافئة لـ NP . ومن المهم أن FP = FNP إذا وفقط إذا كانت P = NP . ^{[ 24 ]}

تُقدّم مسائل الوعد تعريفًا بديلًا لفئات التعقيد القياسية لمسائل القرار. على سبيل المثال، يمكن تعريف P على أنها مسألة وعد: ^{[ 27 ]}

P هي فئة مسائل الوعد التي يمكن حلها في وقت متعدد الحدود حتمي. أي مسألة الوعد${\displaystyle (\Pi _{\text{ACCEPT}},\Pi _{\text{REJECT}})}$يكون في المجموعة P إذا وُجدت خوارزمية زمنية متعددة الحدود${\displaystyle M}$بحيث:

• لكل${\displaystyle x\in \Pi _{\text{ACCEPT}},M(x)=1}$
• للأبد${\displaystyle x\in \Pi _{\text{REJECT}},M(x)=0}$

وبالتالي، فإن فئات مشاكل القرار - أي فئات المشاكل المعرّفة كلغات رسمية - تُترجم بشكل طبيعي إلى مشاكل الوعود، حيث تكون اللغة${\displaystyle L}$في الفصل ببساطة${\displaystyle L=\Pi _{\text{ACCEPT}}}$و${\displaystyle \Pi _{\text{REJECT}}}$هو ضمنيًا${\displaystyle \{0,1\}^{*}/\Pi _{\text{ACCEPT}}}$.

لا يُضيف صياغة العديد من فئات التعقيد الأساسية، مثل P، على شكل مسائل وعد، الكثير من الفهم لطبيعتها. مع ذلك، توجد بعض فئات التعقيد التي كانت صياغتها على شكل مسائل وعد مفيدة لعلماء الحاسوب. على سبيل المثال، لعبت مسائل الوعد دورًا محوريًا في دراسة SZK (المعرفة الصفرية الإحصائية). ^{[ 28 ]}