Beziehung zwischen Komplexitätsklassen

28.11.2022, 13:44

Malcang

Beziehung zwischen Komplexitätsklassen

Hallo zusammen,

ich höre aktuell Komplexitätstheorie und tue mir da schwer. Ich habe nun folgende Aufgabe:

Zitat:

Entscheiden Sie fur jedes der gegebenen Klassenpaare, welche ¨ Klasse in der jeweils anderen als Teilmenge enthalten ist. Begründen Sie Ihre Antworten.

1. $\begin{eqnarray*} NTIME(n^2) \text{ und } DSPACE(n^3) \end{eqnarray*}$
2. $\begin{eqnarray*} DTIME (3n^2+\log(n)^4 \text{ und } DTIME(n^2+1) \end{eqnarray*}$

Wir haben dazu die folgenden Sätze:
[attach]56406[/attach][attach]56402[/attach][attach]56403[/attach][attach]56404[/attach][attach]56405[/attach]

Bei der ersten Aufgabe habe ich folgendes:
Es ist $\begin{eqnarray*} f(n) = n^2 \geq n \Rightarrow NTIME(n^2) \subseteq DPSACE(n^2) \end{eqnarray*}$ nach Satz 6. Und trivialerweise ist $\begin{eqnarray*} DSPACE(n^2)\subseteq DSPACE(n^3) \end{eqnarray*}$ . Damit gilt $\begin{eqnarray*} NTIME(n^2)\subseteq DSPACE(n^3). \end{eqnarray*}$

Ich habe leider keine Idee, wie ich die andere Richtung zeigen kann. Könnt ihr mir einen Denkanstoß geben?

28.11.2022, 17:29

Malcang

Auf diesen Beitrag antworten »

Zu der 2. Aussage habe ich folgendes gemacht:
Es ist $\begin{eqnarray*} \frac{3n^2+\log(n)^4}{n^2+1}\leq 7 \end{eqnarray*}$ und damit ist $\begin{eqnarray*} 3n^2+\log(n)^4 =\mathcal{O}(n^2+1) \end{eqnarray*}$ . Nach Satz 4 ist dann
$\begin{eqnarray*} DTIME(3n^2+\log(n)^4 =DTIME(\mathcal{O}(n^2+1)) = DTIME(n^2+1) \end{eqnarray*}$

28.11.2022, 17:35

IfindU

Auf diesen Beitrag antworten »

Ich kenne nicht die Definition der Räume. Von den Sätzen ausgehend, gilt beim zweiten erst einmal nur eine Teilmengen-Relation, keine Gleichheit. Beim ersten kann ich alles außer $\begin{eqnarray*} DSPACE(n^2)\subseteq DSPACE(n^3) \end{eqnarray*}$ nachvollziehen. Ich glaube dir gerne, dass es trivial folgt, kann es aber nicht nachrechnen.

28.11.2022, 19:03

Malcang

Auf diesen Beitrag antworten »

Hallo IfindU,

sorry, ich habe hier nochmal die Räume:
[attach]56415[/attach]
jede Turingmaschine in $\begin{eqnarray*} DSPACE(n^3) \end{eqnarray*}$ braucht höchstens Platz $\begin{eqnarray*} n^3 \end{eqnarray*}$ und damit auch höchstens $\begin{eqnarray*} n^2. \end{eqnarray*}$ Deshalb habe ich $\begin{eqnarray*} DSPACE(n^2)\subseteq DSPACE(n^3) \end{eqnarray*}$ geschlossen.

Zitat:

Von den Sätzen ausgehend, gilt beim zweiten erst einmal nur eine Teilmengen-Relation, keine Gleichheit.

Hm...ich habe Satz 4 Punkt 2 darauf angewendet verwirrt

Habe ich da einen Fehler gemacht?