PPA (التعقيد)

في نظرية التعقيد الحسابي ، تُعدّ PPA فئة تعقيد ، اختصارًا لـ "حجة التكافؤ متعددة الحدود" (على الرسم البياني). قدّمها كريستوس باباديميتريو عام 1994 ^{[ 1 ]} (صفحة 528)، وهي فئة فرعية من TFNP . وهي فئة من مسائل البحث التي يمكن إثبات كونها شاملة بتطبيق مبرهنة المصافحة : أي رسم بياني غير موجّه يحتوي على رأس درجته عدد فردي، لا بدّ أن يحتوي على رأس آخر درجته عدد فردي . تعني هذه الملاحظة أنه إذا أُعطينا رسمًا بيانيًا ورأسًا بدرجة فردية، وطُلب منا إيجاد رأس آخر بدرجة فردية، فإننا نبحث عن شيء مضمون الوجود (أي أننا أمام مسألة بحث شاملة).

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

يُعرَّف PPAD بطريقة مشابهة لـ PPA، إلا أنه يُعرَّف على الرسوم البيانية الموجهة . يُعد PPAD فئة فرعية من PPA. والسبب في ذلك هو أن المسألة المقابلة التي تُعرِّف PPAD، والمعروفة باسم "نهاية الخط"، يُمكن اختزالها (بطريقة مباشرة) إلى البحث المذكور أعلاه عن رأس إضافي ذي درجة فردية (ببساطة، عن طريق تجاهل اتجاهات الحواف في "نهاية الخط").

• تُعتبر مسألة LONELY مسألة PPA-كاملة: بالنظر إلى دائرة تحدد مطابقة جزئية على${\displaystyle \{0,1\}^{n}}$بحيث${\displaystyle {\vec {0}}}$إذا لم يكن هناك تطابق (يمكن فرض هذه الشروط نحويًا عن طريق معالجة الدائرة)، فابحث عن رأس آخر غير متطابق. ^{[ 2 ]}
• توجد نسخة غير موجهة من مبرهنة سبيرنر معروفة بأنها كاملة بالنسبة لـ PPA. ^{[ 3 ]}
• من المعروف أن مشكلة الإجماع-التقسيم إلى النصف كاملة بالنسبة لـ PPA . ^{[ 4 ]}
• تُعد مشكلة البحث عن دورة هاميلتونية ثانية على رسم بياني منتظم من الدرجة 3 عضوًا في PPA، ولكن من غير المعروف أنها كاملة بالنسبة لـ PPA.
• يوجد اختزال عشوائي متعدد الحدود من مشكلة تحليل الأعداد الصحيحة إلى مشاكل كاملة لـ PPA. ^{[ 5 ]}