Beweisen oder widerlegen folgender Aussagen zu P, NP und Reduktion

Question

Hallo, ich habe eine Frage zur theoretischen Informatik. Es geht um Reduktion, NP und P.

ich bin mir unsicher bei folgenden Aussagen:

1) A ∈ P ∧ B ∈ P ⇒ A\B ∈ P
Meine Antwort: Ich denke die Aussage stimmt nicht.

2) A \(\leq \begin{array}{l} \text {poly} \\ \text {mo} \end{array}\) B ⇒ B \(\leq \begin{array}{l} \text {poly} \\ \text {mo} \end{array}\) A
Meine Antwort: Die Aussage stimmt nicht.

3.) B ≠ Σ* , B ≠ ∅ ∧ A ∈ P ⇒ A \(\leq \begin{array}{l} \text {poly} \\ \text {mo} \end{array}\) B
Meine Antwort: hier weiß ich leider nicht so richtig wie ich das interpretieren soll

Ich habe mir versucht das ganze vorzustellen. Mir sind keine wirklichen Gegenbeispiele eingefallen.

Kann mir einer sagen ob meine Antworten stimmen, bitte? DANKE schon mal im Voraus!

Comments

Was bedeutet \(\leq \begin{array}{l}\text {poly} \\\text {mo}\end{array}\)?

---

Sei \(L\subseteq \Sigma^*\), dann ist \(A\leq_{\operatorname{mo}}^{\operatorname{poly}} B\) genau dann, wenn \(\exists f:\Sigma^*\to \Sigma^* \) total berechenbar in Polynomzeit ist mit \(x\in A \iff f(x)\in B\)

Answer 1

1) A ∈ P ∧ B ∈ P ⇒ A\B ∈ P

x ∈ A kann in polynomieller Zeit p_A(|x|) überprüft werden

x ∈ B kann in polynomieller Zeit p_B(|x|) überprüft werden

x ∈ A\B benötigt maximal die Zeit p_A(|x|) + p_B(|x|).