مراجعة دليلي على أن CO-NP!= P

Question

هذا هو عمل مستوى هواية، وليس وظيفتي. كتبت هذه المقتطف لمشاركة بعض الأفكار حول CO-NP.

الفكرة هي اختيار فئة مشكلة في CO-NP، حيث من الصعب التحقق من الإجابة الصحيحة بسبب تعقيد الدوائر، معبرا عنها كصيغة ساتلة 1 في K، وتظهر هناك أيضا شهادة قصيرة، التي الطول في البتات هو بالضبط ضعف عدد البنود. قد يكون صحيحا أو خاطئا أن جميع مشاكل CO-NP لديها شهادة قصيرة في هذا النموذج (CO-NP؟= NP)، لكنني أظهر أنه بغض النظر عن ذلك، يمكن إجراء الشهادة القصيرة لهذه المشكلة صعبة بشكل تعسفي البحث، بسبب العلاقة المتداولة مع NP. في الأساس، أريد إبراز تبعية دائرية معينة بين أوراكل NP و CO-NP. الحجة إلى STOMP ضد CO-NP= P هي أنه لا يمكن لأي TM أن يأمل في مهاجمة مشكلة البحث عن الشهادة القصيرة في وقت فرعي، لأن الطريقة التي حددتها المشكلة تجعلها تحتوي على كمية تعسفية من "عشوائي حقيقي". في الأساس، فهي وصفة واحدة محددة لبناء مشكلة مشتركة "الوحش" من شهادة بسيطة.

الآن لدي العديد من الأسئلة لأي شخص لديه تدريب أكثر رسمية مني:

• لديه هذه الفئة من المشكلة تم التعبير عن اسم مختلف؟
• هل هذا نهاية مسدود واضحة أو غير مستكشفة؟
• كيف يمكنني التعبير عن نفس الأفكار ولكن أكثر رسميا ضد قدرات TM؟

Answer 1

wtlu في p.

الخوارزمية:

• اجعل مونولا مونولا 1 في k in-k عن طريق إضافة جملة واحدة لكل زوج من الحرفيين (x + ~ x)= 1 واستبدال ~ x مع متغير جديد.
• اختيار رئيس الوزراء كبير، على الأقل أكبر من عدد البنود.
• تحويل صيغة السبت 1 في k إلى نظام المعادلات الخطية modulo p.كل جملة أصلية في النموذج (x، y، z ...)= 1 يصبح معادلا (x، y، z ...)= 1 mod p.
• أداء القضاء غاوسي.
• إذا كانت الصيغة مثيل WTLU، فسيتم العثور على تناقض قبل الوصول إلى نموذج Echelon الخاص بالصف، في شكل معادلة متناقضة 0= K Mod P (مع K!= 0).

لماذا يعمل:

إذا كان هناك مجموعتان من البنود التي تغطي نفس مجموعة الأدوات الحرفية، بحيث (C1 + C2 + C3 ...)= x و (c1 '+ c2' + c3 '...)= y و x!= ذ، ثم هو أيضا حالة modulo ص.وبالتالي، فإن نظام المعادلات MODULO P غير مريض أيضا.

Answer 2

إليك مضاد وثيقة. بنية إثبات مماثلة، يمكن استخدامها بسهولة لإثبات أن XOR-SAT صعب.

1. تأخذ صيغة XOR-Sat غير مرضية مع مساحة كبيرة. لا يمكنك حلها مع خوارزمية تشبه القرار.

2. الآن موجود شهادة عدم التسلية القصيرة، لأن XOR-SAT في P.

3. إذا كنت لا تعرف القضاء، فأنت تجمع بين الجمل العشوائية معا حتى يتمتع بنديان نفس المتغيرات، صف واحد يساوي الصفر والصف الآخر يساوي واحد. Lining Up هي حالة خاصة بالإضافة إلى ذلك، حيث لا يوجد لدى البنود أي حرفي مشترك.

4. أضفت عبوات عشوائية ومتغيرات إلى صيغة XOR-SAT لجعل الأمر أكثر صعوبة في فعل الأشياء بشكل عشوائي.

ولكن في الواقع، يمكنك القضاء على Gaussian في مقدار متعدد الحدود من الوقت والمساحة حتى يلغي الصفوفان بعضهما البعض لإنتاج 0= 1.

لتوسيع نطاق حجتك وجعلها مثيرة للاهتمام، ستحتاج إلى ذلك على الأقل أن هناك فرقا أساسيا مع XOR-SAT، لبدء عدم وجود عملية تشبه القضاء حيث يمكنك إخراج المتغيرات واحدا تلو الآخر أثناء عملية عزل المجموعات المعتادة 2 من البنود أثناء تجاهل المعلومات الإضافية.