Komplexitätsklassen: Problem mit Differenz

Question

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.

Answer 1

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}\)

Comments

Ü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.