لدي مشكلة في القرار بشهادات بحجم 2 ^ n $ بت، كيف يمكنني التحقق من مشكلة قراري بكفاءة إذا كانت في NP $ $؟

Question

مشكلة القرار: هل $ 2 ^ k $ + $ m $ prime؟

المدخلات لكل من $ k $ و $ M $ هي أعداد صحيحة فقط. الحل هو مجموع $ 2 ^ k $ + $ m $ . ( استخدم AKS لاتخاذ قرار رئيس )

صلاحيات 2 لديك تقريبا $ 2 ^ n $ الأرقام. النظر في $ 2 ^ k $ حيث $ K $ = 100000. قارن مقدار الأرقام في $ K $ إلى كمية الأرقام في حلها!

السؤال

يرى أن شهادة مشكلة القرار يمكن أن تكون 2 ^ n $ الحجم، كيف يمكنني التحقق من مشكلة القرار في وقت متعدد الحدود، بالنظر إلى أنني أستطيع أن ننظر فقط إلى الدول الانتقالية كشهادة في حد ذاتها؟

بمعنى آخر، ما الذي يشبه التحقق من الوقت متعدد الحدود مشكلة هذه المشكلة؟

Answer 1

مشكلة في القرار لديها إجابة بنعم / لا، لذلك لا يمكن أن يكون لها "الحجم الأسي".أنت تسأل عن مشاكل البحث، يمكن أن يكون لهؤلاء بالتأكيد حجم الأسي.ونعم، إذا كان حجم الحل (المكتبت في بعض التنسيق المضغوط المناسبة، أي) هو الأسي في حجم المشكلة الأصلية، فمن المستحيل بوضوح حتى كتابة الإجابة في وقت متعدد الحدود.

في أي حال، تنطبق P و NP بدقة فقط على مشاكل القرار.ولكن إلقاء نظرة على Belare's "القرار VS Search" لالعلاقة بين كليهما.