Frage:
Sie die Komplexitätsklasse NDP definiert als:
$$NDP = \left\{A \setminus B | A,B \in NP\right\}$$
Beweise die Aussage:
$$NP \subseteq NDP$$
Leider kriege ich mir da gar keinen Ansatz für vorgestellt.
Wegen \(\emptyset \in \mathrm{NP}\) ist
\(\begin{aligned}\mathrm{NP} &= \left\{A | A \in \mathrm{NP}\right\}\\& = \left\{A \setminus \emptyset | A \in \mathrm{NP}\right\} \\&\subseteq \left\{A \setminus B | A,B \in \mathrm{NP}\right\}\\& = \mathrm{NDP}\text{.}\end{aligned}\)
Über den Fall bin ich auch schon gestolpert, da im nächsten Teil der Aufgabe aber gezeigt werden muss das auch coNP ne Teilmenge von NDP ist, ist das nur der Schluss.
Ich habe auf SO (o.ä) gefunden das die Differenz von A und B nicht notwendigerweise in NP liegen muss. So hat man beides abgedeckt, die Probleme die nicht NP aber NDP sind und alle NP Probleme darin.
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos