0 Daumen
28 Aufrufe

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!

von

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

1 Antwort

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

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

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

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

vor von 2,0 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community