بحاجة إلى توضيح فيما يتعلق بشهادات مشاكل coNP

Question

ملحوظة:هذا هو لا محاولة لإثبات $NP eq coNP$

هناك شيء واحد لم أتمكن مطلقًا من استيعابه تمامًا فيما يتعلق بشهادات المشكلات $coNP$ وسأكون ممتنًا جدًا للحصول على توضيح نهائي من هذا المجتمع.

دعونا نركز على مشكلة مجموع المجموعة الفرعية ($SUBSUM$)، والآن نعلم جميعًا أن هذه المشكلة موجودة $NP$ منذ ذلك الحين ، لقبول عضوية اللغة ، المثل $P_v$ يمكن أن تنبعث منها شهادة وهو التحقق $V_r$ يمكن التحقق من وقت متعدد الحدود.حتى هنا لا مشكلة.تكملة هذه المشكلة ($\overline{SUBSUM}$) في داخل $coNP$ مما يعني أننا لا نعرف ما إذا كان هناك الإيجاز (أي متعدد الحدود) شهادة لتحديد اللغة.إذا كانت هذه الشهادة غير موجودة، ثم $NP eq coNP$ وبالتالي $P eq NP$.ما لا أفهمه هو هذا:

إذا كان لدي (على سبيل المثال) مجموعة $س$ من الأعداد الصحيحة والعدد $0$ كمدخل وأسأل:أثبت لي ذلك $\forall s \in S \space\space\lليس SUBSUM$, ، أي $ موجود$ مجموعة فرعية من $س$ بحيث يعطي مجموع عناصره $0$ ونتيجة لذلك (هذا $\overline{SUBSUM}$, ، تكملة مشكلة المجموعة الفرعية).كيف يمكن وجود شهادة لهذه المشكلة التي تم التحقق منها $P$؟أعني أنني بحاجة لإثبات ذلك لكل المجموعة الفرعية لذا يجب أن تكون مساحة البحث هي مجموعة الطاقة $س$.لو $|S|=ن$ ثم $\mathcal{|P(S)|}=2^n$.لذلك إذا كان المُثبِّت، على سبيل المثال، ينتج أ $2^{ن/3}$ الشهادة، وهذا يعني أنني أترك بشكل منهجي $2^{ \frac{2}{3}n}$ مجموعات فرعية.ما لا أفهمه تمامًا والذي أحتاج إلى توضيحه هو سبب عدم قبول هذه الحجة كدليل على ذلك $NP$ لم يتم إغلاقه تحت المكمل.

Answer 1

الدليل على أن الروبوت يجب أن يكون مجموعة فرعية.قد يكون هذا مؤشرًا آخر على أن المجموعة المحددة لديها بعض القيود التي تمنعها من أن تكون مثالًا إيجابيًا لمشكلة المجموعات الفرعية.ومن الأمثلة الجيدة على الشهادة غير التافهة البرمجة الخطية.تقبل البرامج الخطية كلاً من الشهادة الإيجابية والسلبية (بالنسبة لسؤال ما إذا كان الأمثل يمكن أن يكون أصغر/أكبر من القيمة k).المثال الإيجابي هو بالطبع تعيين للمتغير.لكن السلبية تعطى من قبل فاراكس والازدواجية الضعيفة.

التمرين الجيد بالنسبة لك هو البحث عن البرامج الخطية والازدواجية الضعيفة و Farkas lemma :)