هل P= NP في Automata الخلوي من المساحات القطعي؟

Question

قرأت منذ بضع سنوات في هذا الكتاب هذا

من فهمي، P= NP مشكلة تبحث عن خوارزميات متعددة الحدود حل المشاكل المعقدة. من لموهيتي السريعة من خلال الكتب والأوراق، يبدو أنه يشير إلى حل المشكلة. ما أنا في عداد المفقودين؟

href="https://pdfs.semanticscholar.org/57b8/bb57d9e8c8e699ccb54d4fb98c54f1a417d0.pdf" rel="nofollow noreferrer"> هنا هو ورقة أخرى، بعنوان في بعض المساحات المنحنية، نحن يمكن حل مشاكل NP-Hard في وقت متعدد الحدود: نحو حلم Matiyasevich .

Answer 1

مشكلة P. NP هي سؤال حول آلات Turing $ T $ ، لأن فئات التعقيد P و NP محددة من حيث هذه الآلات النظرية. دعونا ندعو هذه الفئات $ p_t $ و $ np_t $ من الآن فصاعدا. تقدم الورقة آلة حساب نظري جديد $ H $ التي تحتوي على الفئات المرتبطة $ p_h $ (يعمل في كثير الحدود الوقت على Automaton الخلوي القطعي) و $ np_h $ (يعمل في وقت متعدد الحدود غير المحدد في Automaton الخلوي القطعي).

الخطوة الأولى في هذه الورقة دليل على أن مشكلة 3SAT، والمعروفة جيدا $ np_t $ ، يمكن حلها في وقت متعدد الحدود على هذا الجهاز ، أي تكمن هذه المشكلة في $ p_h $ . بعد ذلك، يظهرون أي تقليل وقت متعدد الحدود في آلة تورينج يمكن أن يتم تنفيذها في وقت متعدد الحدود على Automaton Hyperbolic. منذ 3SAT $ np_t $ -complete، أي $ np_t $ يمكن تخفيضها إلى مثيل 3SAT في متعدد الحدود (على $ t $ بحكم التعريف، لذلك أيضا على $ H $ بواسطة Lemma) ثم يتم حلها عن طريق حل 3SAT في بولي وقت، كلاهما في Automaton القطعي. بمعنى آخر، يمكن كتابة النتيجة الرئيسية لهذه الورقة (Theorem 1) ك $ np_t \ subseteq p_h $ في تدويننا. هذا لا يعطي حلا لمكينة P مقابل NP، لأن ذلك سيحتاج إلى ربط الفصول $ np_t $ و $ p_t $ .

لاحظ أن المؤلفين تتضمن بعض الملاحظات حول مشكلة P مقابل NP في القسم 4.2، حيث يزعمون أن نتائجهم هي دليل على P $ \ NEQ $ np ( !):

يتكون الاتجاه الثالث من الضوء الجديد على سؤال P= NP في الإعدادات العادية. نظرا لأن مساحة القطعي لديها خصائص مختلفة تماما عن خصائص مساحة Euclidean، على وجه الخصوص، فإن لديها العديد من الاتجاهات، لن تكون تلميحا مواتية لإثبات أن P $ \ NEQ $ np في ظروف euclidean؟ يبدو أن على مدى السنوات العشر الماضية الأعمال في مجال تعقيد يميل الناس إلى تصديق أكثر في P $ \ NEQ $ np. على ما يبدو، فإن النتيجة الحالية تنتمي أيضا إلى هذا الاتجاه.