الجمع بين 2 من مشاكل في NP في واحد

Question

قلت القطعية آلة تورينج الذي يحل قرار المشكلة S مع أوراكل الوصول إلى كل المشاكل B, C التي هي في $NP$.يمكن دا يكون حلها مع أوراكل الوصول إلى فقط واحد المشكلة في $NP$?

أن ب و ج بطريقة ما تكون مجتمعة في مشكلة واحدة في $NP$ (وهكذا تظهر الصورة في $P^{NP}$)?

Answer 1

هناك اثنين على الأقل من الطرق للقيام بذلك.الأول هو أن تأخذ منفصلة مجموع $B$ و $C$, التي يمكن أن يتم بطرق عديدة, على سبيل المثال $$ \{0 x :x \in B\} \كأس \{1y :y \C\}.$$ والثاني هو استخدام NP-complete اللغة $L$ كما oracle.لأن أي مشكلة في NP يقلل إلى $L$ في وقت متعدد الحدود ، يمكنك محاكاة $B$-أوراكل باستخدام $L$-أوراكل.