هي البراهين NP تقتصر على طول متعدد الحدود؟

Question

في نظرية التعقيد الحاسوبية، NP (الوقت متعدد الحدود غير المرن) هو فئة التعقيد تستخدم لتصنيف مشاكل القرار.NP هي مجموعة مشاكل القرارات التي تكون مثيلات المشكلات، حيث تكون الإجابة "نعم"، لها دليل يمكن التحقق منه في الوقت متعدد الحدود بواسطة آلة تورينجية حتمية.

يتم التحقق من البراهين لمشكلة قرار NP في وقت متعدد الحدود.

هل هذا يعني البراهين في معظم طول كثير الحدود؟

"حسنا، عليك قراءة المدخلات بأكملها. إذا كانت الإدخال أطول من متعدد الحدود، فهذا الوقت أكبر من متعدد الحدود."

مشكلة القرار "هي القليل الأول من المدخلات A 0؟"يمكن حلها في الوقت المستمر والمساحة - دون قراءة المدخلات بأكملها.

لذلك، ربما تحتوي بعض مشكلة NP على براهين مرشح أطول من طول متعدد الحدود ولكن فحصها في وقت متعدد الحدود.

Answer 1

مشكلة القرار "هي القليل الأول من المدخلات A 0؟"يمكن حلها في الوقت المستمر والمساحة - دون قراءة المدخلات بأكملها.

نظرا لأن رئيس آلة Turing يتحرك خطوة واحدة في المرة الواحدة، يمكن لرأس آلة Turing فقط قراءة كمية متعددة الحدود من الإثبات في وقت متعدد الحدود.

بينما يمكنك تحديد البراهين لتجاوز الطول متعدد الحدود، يمكن قراءة بادئة متعددة الحدود للدليل في الوقت متعدد الحدود، على افتراض أن الرأس يبدأ في الخلية 0 ويمكن أن يتحرك في كحد أقصى خلية واحدة إلى اليمين في وحدة زمنية واحدة.

Answer 2

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

غير معروف ما إذا كانت جميع البراهين على مثيلات "لا" يمكن التحقق منها في وقت متعدد الحدود والمساحة (الفرق بين NP و CO-NP).

للإجابة على السؤال على وجه التحديد، فإن إثبات مثيل "نعم" هو قيمة الإدخال.لا يمكنك القول أن الإدخال يحتوي على طول متعدد الحدود لأن كثير الحدود يتم استخدامها عند مقارنة بحجم الإدخال.لذلك السؤال لا معنى له بسبب كلمة "كثير الحدود".إذا كنت تريد حقا متعدد الحدود في مكان ما، فيمكن تعريف حجم الإثبات نسبيا إلى الإدخال كدالة خطية F (x)= AX + B حيث= 1 و B= 0، والذي يمكن تبسيطه إلى F (x)= x لأن حجم الإدخال يساوي نفسه.