يحدد إمكانية التحصيل لأنظمة المعادلات التربيعية مع المعاملات العددية عبر العقود في NP؟

Question

في كتاب "تعقيد حسابي" من قبل Arora و Barak يتم طرح السؤال التالي (التمرين 2.20.):

دع realquadeq يكون لغة جميع مجموعات الرضا من المعادلات التربيعية على المتغيرات الحقيقية. أظهر أن realquadeq هو np-complete.

أعرف كيفية إظهار صلابة NP، لكنني عالق عندما يتعلق الأمر بالإثبات أن هذه المشكلة موجودة في NP، ولا سيما كيفية إظهار أننا يمكن أن تصف حلا باستخدام عدد متعدد الحدود من البتات.

قمت ببعض الأبحاث ووجدت أنه عبر الأرقام المعقدة، لا يزال سؤالا مفتوحا إذا كانت المشكلة في NP [1]. كما يبدو يرتبط ارتباطا وثيقا بالنظرية الوجودية للحرر، والتي لم يكن معروفا مرة أخرى في NP.

وبالتالي سؤالي: هل هذه المشكلة معروفة أن تكون في NP؟ وإذا كان الأمر كذلك، فهل يمكن لشن شخص ما في الاتجاه الصحيح فيما يتعلق بالدليل.

---

[1] Pascal Koiran، Hilbert's Nullstellensatz في التسلسل الهرمي متعدد الحدود، مجلة التعقيد 12 (1996)، لا. 4، ص 273-286.

Answer 1

هذه المشكلة (عادة ما يسمى Quad) في الواقع إكمال للحصول على نظرية الوجودية للحرر، وبالتالي إظهار عضوية NP - ستكون نتيجة رائعة وغير متوقعة.يبدو أن أرورا وباراك تهدف فقط إلى طلب دليل على صلابة NP.