عدم كفاءة 2 مشاكل برضية منطقية

Question

أتوسل بعض المساعدة في هذه المشكلة.

هناك 2 مشاكل لراض منطقية.

مشكلة $ $ : تحديد ما إذا كانت صيغة تعسفية الحجم $ n $ هي $ $ $ .
مشكلة $ B $ : تحديد ما إذا كانت صيغة تعسفية للحجم $ n-1 $ هي $ $ حيث $ n $ هو عدد صحيح $ \ ge 2 $

أثبت أن $ A $ يمكن أن يكون قابلة للحل إذا كان $ B $ غير قابل للحل.

أعتقد أن الحل سوف يظهر أن $ $ هو اختزال $ B $ وبعد وهذا يعني أنه يجب علي إظهار خوارزمية Oracle من $ B $ تستمد خوارزمية Oracle من $ $ .

كما ترون، الصيغة التعسفية من $ B $ هي $ n-1 $ ، ولكن أن $ $ هو $ n $ . كيف يمكنني أن أفترض أن أستلزم خوارزمية Oracle حول $ $ من Oracle of $ b $ ، والتي يحدد صيغة حجم 1 أقل من حجم $ B $ ؟

Answer 1

مشكلة متوقفة للمشكلة ب بالطريقة التالية:

• اختيار متغير في المشكلة A وضبطه 0
• الآن لدينا صيغة الحجم N-1، إذا كان راضيا مع B ثم إرجاع الرفض
• آخر، اختر مشكلة مرة أخرى وتعيين المتغير إلى 1
• الآن لدينا صيغة الحجم N-1 مرة أخرى، إذا كانت راضية مع B ثم إرجاع رضا آخر عودة غير مرضية غير مرضية

بعبارة أخرى: انقسام مشكلة في مشكلتين ب باستخدام أي متغير.إذا كانت B التي تقول غير مرضية لكلا من 0 و 1 فمن غير مرتهبا.إذا كان الأمر يتعلق برضا لمدة واحد على الأقل من الاثنين، فمن الراضي.