مرجع
آخر الزيارات

PH(التعقيد الحسابي)

117 كلمة•0 مشاهدة•🗒️ منذ يوم
باختصار: في نظرية التعقيد الحسابي الصنف PH هو توحيد كل الاقسام في هرمية كثيرة الحدود. تجد هنا «تعريف» و«قسم تعقيد».
المحتويات
  1. تعريف
  2. قسم تعقيد

قبل الخوض في التفاصيل، في نظرية التعقيد الحسابي الصنف PH هو توحيد كل الاقسام في هرمية كثيرة الحدود. لقد تم تعريف هذا القسم لأول مرة بواسطة لاري ستوكماير. وهذا القسم يتبع P#P = PPP وكذلك يتبع بيسبايس. وتعرض الأقسام التالية جوانب أخرى من الموضوع.

وعلى صعيد آخر، PH يحتوي أغلب الاقسام في بيسبايس مثل: NP ,P,كو-إن بي كما أنه يحوي اقسام تعقيد احتمالية مثل: BPP , RP , ولكن هناك دلائل على أنَّ BQP لا يتبع PH .

من جهة ثانية، P=NP إذا وفقط إذا PH=P لذا فانه كفاية أن يُبرهن أنَّ P≠PH لكي نبرهن أن P≠NP .

تعريف

انظر كذلك

مراجع

ومن ناحية أخرى، في حين أن إذا يوجد آلة تيورنج كثيرة الحدود قطعية،M, ويوجد متعدد حدود (q(n بحيث أن n هو طول المدخل، ويتحقق: في حين أنَّ

قسم تعقيد

مسألة P=NP

نظرية التعقيد الحسابي.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.