خوارزمية زمنية متعددة الحدود غير المرنة مقابل شهادة / مدقق لإظهار العضوية في NP

Question

في هذه الورقة ( https://arxiv.org/pdf/1706.06708.pdf ) يثبت المؤلفون أن يحلون على النحو الأمثل $ n \ times n \ times n $ cube's cube هو مشكلة كاملة NP. في هذه العملية، يجب عليهم إظهار أن مشكلة القرارات ذات الصلة تنتمي إلى NP (القسم 2.5 في الصفحة 6). للقيام بذلك، يصفون الخوارزمية التي تحل المكعب nondeterministically في وقت متعدد الحدود. يبدو لي أن هذا هو جهد أكثر من اللازم.

على وجه الخصوص، فإن مشكلة القرار ذات الصلة هي كما يلي: مشكلة مكعب روبيك لديها كمدخل التقليب $ T $ وقيمة $ K $ . الهدف هو تحديد ما إذا كان يمكن حل $ t $ في $ K $ أو أقل من التحركات. وبالتالي بدلا من إنشاء خوارزمية حلول زمنية متعددة الحدود غير المرن، يمكنها ببساطة إعطاء شهادة أن قرار "نعم" هو مجرد قائمة بموجبها $ K $ التحركات والتحقق منها أن التحقق من هذا هو وقت متعدد الحدود.

لذلك أسئلتي هي كما يلي. هي التعريفي أدناه معادل في الواقع؟

1. np هو فئة التعقيد من مشاكل القرار القابلة للحل بواسطة آلة تورينج ناسطة في وقت متعدد الحدود.
2. np هو فئة التعقيد من مشاكل القرار التي يمكن تأكيد حلها في وقت متعدد الحدود (حاسما)؟

وإذا كانت معادلة، فلماذا فإن مؤلفي الورقة المرتبطة اختيار الطريقة الأكثر صعوبة (أو أنا مخطئ في هذا الافتراض)؟

---

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

Answer 1

الشهادة التي تقترحها قد لا تكون متعدد الحدود في حجم الإدخال.

حجم الإدخال للمشكلة هو $ o (n ^ 3 + \ log k) $ ، في حين أن شهادتك لديها حجم $ \ أوميغا (k \ log n) $ .هذا ليس متعدد الحدود، على سبيل المثال، ل $ k= 2 ^ n $ .

شهدتك تعمل إذا قمت بتعيينه، على سبيل المثال، إلى قائمة فارغة كلما $ k=omega (\ frac {n ^ 2} {\ log n}) $ ، وتعديل المدقق لمجرد التحقق مما إذا كان تكوين الإدخال للمكعب قابل للحل لأي قيمة من هذا القبيل من $ K $ (وبالتالي تجاهل الشهادة).