0 Daumen
399 Aufrufe

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.

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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

Avatar von 5,7 k

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

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community