تورينغ عدم قابلية إصدارات مشكلة الاستيفاء

Question

أحتاج إلى مساعدة في هذه المشكلة.

هناك إصدارات من مشكلة الإرضاء:

[1] إصدار القرار: حدد ما إذا كانت صيغة تعسفية F هي راضي أم لا

[2] إصدار البحث: إذا كانت صيغة تعسفية F مرضية، والعودة تعيين قيم الحقيقة للمتغيرات في الصيغة التي تجعل و راضي.إذا كانت F غير مرضية، فارجع nil.

إظهار أن [2] يذين متوفرة إلى [1].

يجب أن أثبت أن خوارزمية أوراكل من [1] تستلزمها [2] أن نقول "[2] تورينج لا تقليل [1]".

أرى أن [2] هو مجرد خوارزمية أوراكل من [1] لأنه يميز لارتياح صيغة تعسفية و.

هل يمكن أن يعني هذا خوارزمية أوراكل من [1] أن [2]؟إذا كان يمكن، ماذا سيكون السبب؟

Answer 1

أي خوارزمية تقرر أن تستخدم إرضاء الصيغة للعثور على مهمة لصالح صيغة راضية:

بينما لم يتم تعيين جميع المتغيرات:

• اختر متغيرا واختر قيمة 0.

• إذا لم تعد الصيغة راضية، فاستبدل القيمة مع 1.