إذا كانت مشكلة القرار في $ P $، فيجب أن تكون إيجاد الحل ممكن في وقت متعدد الحدود؟
-
29-09-2020 - |
سؤال
مشكلة الوظيفة التي تجد الحل
-
أعطى عدد صحيح $ n $ .
-
find $ 2 $ أعداد صحيحة متميزة عن $ n $ .(ولكن أقل من $ n $ )
-
يحتوي على منتج يساوي $ n $ .
هذا يعني أنه يجب علينا استبعاد الأعداد الصحيحة $ 1 $ و $ n $ .
خوارزمية هي pseudo-polynomial
giveacodicetagpre.الإخراج
giveacodicetagpre.الخوارزمية التي تحل مشكلة القرار
giveacodicetagpre.السؤال
منذ مشكلة القرار في $ P $ يجب أن تجد حلا أيضا قابلة للحل في وقت متعدد الحدود؟
المحلول
لا، والمثال الذي تدرجه هو مثال كلاسيكي: بقدر ما نعرفه، لا يبدو أن العوملة لا يبدو أنه $ P $ ، ولكن تحديد ما إذا كانالرقم هو بالتأكيد في $ p $ .
مثال آخر: النظر في اللعبة Hex .النظر في مشكلة القرار: معطى $ n $ ، حدد ما إذا كان لدى اللاعب الأول استراتيجية رابحة ل Hex على $ n \Times N $ هناك مشكلة الوظيفة المقابلة: معمل $ n $ ، ابحث عن هذه الاستراتيجية الفائزة.حسنا، مشكلة القرار تافهة (من المعروف أن الجواب هو دائما "نعم")، ولكن تعتقد أن مشكلة الوظيفة صعبة للغاية (بقدر ما نعرف).