قائمة فئات التعقيد
هذه قائمة بفئات التعقيد في نظرية التعقيد الحسابي . للاطلاع على مواضيع أخرى في مجال الحوسبة والتعقيد، انظر قائمة مواضيع الحوسبة والتعقيد .
تضم العديد من هذه الفئات نظيراً "مكملاً" يتألف من مكملات جميع اللغات في الفئة الأصلية. على سبيل المثال، إذا كانت اللغة L تنتمي إلى فئة NP، فإن مكمل L ينتمي إلى فئة co-NP. (لا يعني هذا بالضرورة أن مكمل NP هو co-NP، فهناك لغات معروفة بانتمائها إلى كلتا الفئتين، ولغات أخرى معروفة بعدم انتمائها إلى أي منهما).
تشير "أصعب المشاكل" في فئة معينة إلى المشاكل التي تنتمي إلى تلك الفئة بحيث يمكن اختزال كل مشكلة أخرى من تلك الفئة إليها.
| 8S | حساب عدد حلول مسألة NP |
| مكتمل | أصعب المسائل في البرمجة الخطية |
| 2-EXPTIME | يمكن حلها في وقت أسي مزدوج |
| AC 0 | فئة تعقيد الدوائر ذات العمق المحدود |
| ACC 0 | فئة تعقيد الدوائر ذات العمق المحدود وبوابات العد |
| مكيف هواء | فئة تعقيد الدوائر |
| أه | التسلسل الهرمي الحسابي |
| وكالة أسوشيتد برس | فئة المسائل التي يمكن لآلات تورينج المتناوبة حلها في وقت متعدد الحدود. [ 1 ] |
| APX | مسائل التحسين التي تحتوي على خوارزميات تقريب بنسبة تقريب ثابتة [ 1 ] |
| أكون | يمكن حلها في وقت متعدد الحدود بواسطة بروتوكول آرثر-ميرلين [ 1 ] |
| بي بي بي | يمكن حلها في وقت متعدد الحدود باستخدام خوارزميات عشوائية (الإجابة على الأرجح صحيحة) |
| BPL | مشاكل قابلة للحل في مساحة لوغاريتمية ووقت متعدد الحدود باستخدام آلات تورينج الاحتمالية ذات الخطأ ثنائي الجانب |
| BQP | يمكن حلها في وقت متعدد الحدود على جهاز كمبيوتر كمومي (الإجابة على الأرجح صحيحة) |
| co-NP | يمكن التحقق من إجابات "لا" في وقت متعدد الحدود بواسطة آلة غير حتمية |
| مكتملة جزئيًا من نوع NP | أصعب المشاكل في co-NP |
| DLIN | يمكن حلها بواسطة آلة تورينج متعددة الأشرطة حتمية في وقت O ( n ). |
| DSPACE( f ( n )) | يمكن حلها بواسطة آلة حتمية ذات مساحة O ( f ( n )). |
| DTIME( f ( n )) | يمكن حلها بواسطة آلة حتمية في زمن O ( f ( n )). |
| هـ | يمكن حلها في وقت أسي باستخدام أس خطي |
| ابتدائي | اتحاد الطبقات في التسلسل الهرمي الأسي |
| الفضاء | قابلة للحل باستخدام فضاء أسي ذي أس خطي |
| تاريخ انتهاء الصلاحية | نفس وقت التجربة |
| إكسب سبيس | قابلة للحل باستخدام مساحة أسية |
| وقت الخبرة | يمكن حلها في وقت أسي |
| ممرض ممارس عائلي | نظير NP لمسائل الدوال |
| FP | نظير P لمسائل الدوال |
| FP NP | نظير مسألة P NP لمسائل الدوال؛ موطن مسألة البائع المتجول |
| FPT | قابل للمعالجة بمعاملات ثابتة |
| GapL | يمكن اختزالها في فضاء اللوغاريتمات إلى حساب المحدد الصحيح للمصفوفة |
| الملكية الفكرية | يمكن حلها في وقت متعدد الحدود بواسطة نظام إثبات تفاعلي |
| ل | قابلة للحل باستخدام مساحة لوغاريتمية (صغيرة) |
| LOGCFL | يمكن اختزال مساحة السجل إلى لغة خالية من السياق |
| ماجستير | يمكن حلها في وقت متعدد الحدود باستخدام بروتوكول ميرلين-آرثر |
| كارولاينا الشمالية | يمكن حلها بكفاءة (في وقت متعدد اللوغاريتمات) على الحواسيب المتوازية |
| شمال شرق | يمكن حلها بواسطة آلة غير حتمية في وقت أسي ذي أس خطي |
| NESPACE | يمكن حلها بواسطة آلة غير حتمية ذات فضاء أسي ذي أس خطي |
| نيكست | نفس الشيء بالنسبة لـ NEXPTIME |
| نيكسبس | يمكن حلها بواسطة آلة غير حتمية ذات فضاء أسي |
| نيكست تايم | يمكن حلها بواسطة آلة غير حتمية في وقت أسي |
| هولندا | يمكن التحقق من إجابات "نعم" باستخدام المساحة اللوغاريتمية |
| NLIN | يمكن حلها بواسطة آلة تورينج متعددة الأشرطة غير حتمية في وقت O ( n ). |
| غير ابتدائي | مكمل لـ ELEMENTARY . |
| NP | يمكن التحقق من إجابات "نعم" في وقت متعدد الحدود (انظر فئات التعقيد P و NP ) |
| NP-complete | أصعب المشاكل أو أكثرها تعبيرًا في NP |
| NP-easy | نظير لـ P NP لمسائل الدوال ؛ اسم آخر لـ FP NP |
| مكافئ NP | أصعب المشاكل في FP NP |
| NP-hard | لا تقل صعوبة عن أي مسألة في فئة NP، ولكن من غير المعروف أنها تنتمي إلى نفس فئة التعقيد. |
| NSPACE( f ( n )) | قابلة للحل بواسطة آلة غير حتمية ذات مساحة O ( f ( n )). |
| NTIME( f ( n )) | يمكن حلها بواسطة آلة غير حتمية في وقت O ( f ( n )). |
| P | يمكن حلها في وقت متعدد الحدود |
| مكتملة P | أصعب المشاكل في لغة البرمجة P التي يمكن حلها على الحواسيب المتوازية |
| بولي | يمكن حلها في وقت متعدد الحدود بالنظر إلى "سلسلة نصائح" تعتمد فقط على حجم المدخلات |
| PCP | برهان قابل للتحقق احتماليًا |
| درجة الحموضة | اتحاد الطبقات في التسلسل الهرمي متعدد الحدود |
| PL | قابلة للحل في وقت متعدد الحدود باستخدام آلة عشوائية ذات مساحة لوغاريتمية باحتمالية أكبر من 1/2 |
| P NP | يمكن حلها في وقت متعدد الحدود باستخدام وسيط لمسألة في فئة NP؛ تُعرف أيضًا باسم Δ 2 P |
| PP | احتماليًا متعدد الحدود (الإجابة صحيحة باحتمال يزيد قليلاً عن 1/2) |
| PPAD | حجج التكافؤ متعددة الحدود على الرسوم البيانية الموجهة |
| العلاقات العامة | يمكن حلها عن طريق بناء الدوال الحسابية بشكل متكرر. |
| بي سبيس | قابلة للحل باستخدام فضاء متعدد الحدود. |
| برنامج PSPACE-complete | أصعب المسائل في اختبار PSPACE. |
| PTAS | مخطط تقريبي متعدد الحدود (فئة فرعية من APX). |
| برنامج تحسين الجودة | يمكن حلها في وقت متعدد الحدود بواسطة نظام إثبات تفاعلي كمي. |
| QMA | نظير كمي لـ NP . |
| R | يمكن حلها في فترة زمنية محددة. |
| يكرر | مشاكل يمكننا الإجابة عليها بـ "نعم" في فترة زمنية محددة، ولكن قد لا تأتي إجابة "لا" أبداً. |
| RL | يمكن حلها باستخدام مساحة لوغاريتمية بواسطة خوارزميات عشوائية (الإجابة "لا" صحيحة على الأرجح، والإجابة "نعم" صحيحة بالتأكيد) |
| آر بي | يمكن حلها في وقت متعدد الحدود بواسطة خوارزميات عشوائية (الإجابة "لا" صحيحة على الأرجح، والإجابة "نعم" صحيحة بالتأكيد) |
| SL | تُختزل مسائل فضاء اللوغاريتم إلى تحديد ما إذا كان هناك مسار بين رؤوس معينة في رسم بياني غير موجه. في أكتوبر 2004 ، اكتُشف أن هذه الفئة تساوي في الواقع L. |
| S 2 P | ألعاب من جولة واحدة مع تحركات متزامنة يتم تحكيمها بشكل حتمي في وقت متعدد الحدود [ 2 ] |
| TFNP | مسائل الدوال الكلية القابلة للحل في وقت متعدد الحدود غير حتمي. تتميز المسألة في هذه الفئة بأن لكل مدخل مخرجًا يمكن التحقق من صحته بكفاءة، ويكمن التحدي الحسابي في إيجاد مخرج صحيح. |
| أعلى | دوال متعددة الزمن غير حتمية وغير مبهمة. |
| ZPL | يمكن حلها بواسطة خوارزميات عشوائية (الإجابة صحيحة دائمًا، ومتوسط استخدام المساحة لوغاريتمي) |
| ZPP | يمكن حلها بواسطة خوارزميات عشوائية (الإجابة صحيحة دائمًا، ومتوسط وقت التشغيل متعدد الحدود) |
مراجع
روابط خارجية
- حديقة التعقيد - قائمة تضم أكثر من 500 فئة من فئات التعقيد وخصائصها
فئات :
- فئات التعقيد
- قوائم متعلقة بالرياضيات