الجمع بين 2 من مشاكل في NP في واحد
-
29-09-2020 - |
سؤال
قلت القطعية آلة تورينج الذي يحل قرار المشكلة S مع أوراكل الوصول إلى كل المشاكل B, C التي هي في $NP$.يمكن دا يكون حلها مع أوراكل الوصول إلى فقط واحد المشكلة في $NP$?
أن ب و ج بطريقة ما تكون مجتمعة في مشكلة واحدة في $NP$ (وهكذا تظهر الصورة في $P^{NP}$)?
المحلول
هناك اثنين على الأقل من الطرق للقيام بذلك.الأول هو أن تأخذ منفصلة مجموع $B$ و $C$, التي يمكن أن يتم بطرق عديدة, على سبيل المثال $$ \{0 x :x \in B\} \كأس \{1y :y \C\}.$$ والثاني هو استخدام NP-complete اللغة $L$ كما oracle.لأن أي مشكلة في NP يقلل إلى $L$ في وقت متعدد الحدود ، يمكنك محاكاة $B$-أوراكل باستخدام $L$-أوراكل.
لا تنتمي إلى cs.stackexchange