"نظرا لخوارزمية، حدد ما إذا كان يعمل في وقت متعدد الحدود" هل هذه المشكلة في NP؟

Question

هذه المشكلة غير صالحة (متوقعة لوقف المشكلة) ولكنها نصف مرسومة وهناك يمكن التحقق منها (كما تعادل هذه التعريفات: كيفية إثبات شبه مرسوم= التحقق من التحقق منه؟ ).

ومع ذلك، هل هذه مشكلة بولي وقت يمكن التحقق منه؟

مشكلة في القرار $ p $ هو بولي الوقت يمكن التحقق منها IFF هناك خوارزمية

Answer 1

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

لماذا في الوقت الأسي؟لأن $ v يعمل في الوقت المناسب $ | w | ^ k $ ، يمكن أن تقرأ في معظم $ | w | ^ k $ بت المدخلات.لذلك، يكفي لتعداد جميع الأوتار الممكنة $ C $ الطول على الأكثر $ | w | ^ k $ ، وتشغيل $ v $ على كل منها.سيكون وقت التشغيل حول $ 2 ^ ^ {| w | ^ k} $ ، وهو محدود، وبالتالي كافية لجعل المشكلة الأصلية.