التكافؤ P

في نظرية التعقيد الحسابي ، تُعرف فئة التعقيد ⊕ P (تُنطق "باريتي P") بأنها فئة مسائل القرار التي يمكن حلها بواسطة آلة تورينغ غير حتمية في وقت متعدد الحدود ، حيث يكون شرط القبول هو أن يكون عدد مسارات الحساب المقبولة فرديًا. مثال على مسألة ⊕ P هو: "هل يحتوي رسم بياني مُعطى على عدد فردي من التطابقات التامة ؟" . وقد عرّف باباديميتريو وزاكوس هذه الفئة عام 1983. ^{[ 1 ]}

من الأمثلة على المسائل الكاملة من النوع ⊕P ( في ظل اختزالات متعددة الواحدات ذات زمن متعدد الحدود ) مسألة ⊕SAT: هل عدد القيم المُرضية لصيغة منطقية معينة فردي؟ وينتج هذا من برهان نظرية كوك-ليفين لأن الاختزال المستخدم مُقتصد . ^{[ 2 ]}

⊕ P هي فئة عدّ، ويمكن اعتبارها إيجاد البت الأقل أهمية في إجابة المسألة المقابلة رقم P. أما مسألة إيجاد البت الأكثر أهمية فتقع في PP . يُعتقد أن PP فئة أصعب بكثير من ⊕ P ؛ فعلى سبيل المثال، يوجد كون نسبي (انظر آلة أوراكل ) حيث P = ⊕ P ≠ NP = PP = EXPTIME ، كما أوضح بيجل وبورمان وفورتنو في عام 1998. ^{[ 3 ]}

بينما تُبيّن نظرية تودا أن P ^PP تحتوي على PH ، فإنه من غير المعروف أن الفئة P ^{⊕ P} تحتوي حتى على NP . ومع ذلك، يُبيّن الجزء الأول من برهان نظرية تودا أن BPP ^{⊕ P} تحتوي على PH . وقد كتب لانس فورتناو برهانًا موجزًا ​​لهذه النظرية. ^{[ 4 ]}

تحتوي المجموعة ⊕P على مسألة التماثل الذاتي للرسوم البيانية ، وفي الواقع، تُعتبر هذه المسألة منخفضة بالنسبة للمجموعة ⊕P . [ ^{5 ] كما} أنها تحتوي بشكل بديهي على المجموعة UP ، لأن جميع حلول المسائل في UP إما أن يكون لها مسار قبول واحد أو لا مسار قبول على الإطلاق. وبشكل أعم، تُعتبر المجموعة ⊕P منخفضة بالنسبة لنفسها، مما يعني أن مثل هذه الآلة لا تكتسب أي قوة من قدرتها على حل أي مسألة من مسائل ⊕P بشكل فوري.

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

• حديقة التعقيد : تكافؤ الفئة P