Berechenbarkeit und Komplexität MC Test
Vorbereitung für den Multiple Choice Test in Berechenbarkeit und Komplexität
Vorbereitung für den Multiple Choice Test in Berechenbarkeit und Komplexität
-
- 1 / 24
-
Flashcards
Sei \(f:\mathbb{N}\rightarrow \Sigma^*\) eine totale und berechenbare Funktion und \(L=\{f(n)|n\in\mathbb{N}\}\). Dann ist stets
Sei \(L=\{M| |T(M)|\ge5\}\). Dann gilt
Es gibt keine...
Was besagt der Gödelsche Unvollständigkeitssatz?
Sei L die Sprache aller \(w\in \{0,1\}^*\) mit \(T(M_w)=\emptyset\).
Welche der folgenden Aussagen ist falsch?
Sei \(f:\mathbb{N}\rightarrow \{0,1\}\) die Funktion, die Primzahlen auf 1 abbildet und alle anderen Zahlen auf 0-
Sei \(L=\{ww|w\in \{a,b\}^*\}\).
Welche der folgenden Aussagen ist nicht korrekt?
Wir betrachten das Leerheits- sowie das Endlichkeitsproblem für den Schnitt von kontextsensitiven Sprachen, d.h. auf Eingabe zweier Typ-1-Grammatiken \(G_1\) und \(G_2\) ist zu entscheiden, ob \(L(G_1)\cap L(G_2)=\emptyset\) gilt bzw. ob \(L(G_1)\cap L(G_2)\) endlich ist.
Sei \(f(n)=\cases{1, f} \begin{cases} 1 & \mbox{falls ein gerades} \ m \ge n \ \mbox{existiert, das nicht Summe zweier Primzahlen ist} \\ 0& \mbox{sonst} \end{cases} \)
und \(g(n)= \begin{cases} 1 &\mbox{falls die Riemann Hypothese gilt } \\ 0 & \mbox{sonst} \end{cases} \)
Dann ist
Sei L die Sprache aller \(w\in \{ 0,1\}^* \), so dass \(T(M_w)\) nicht semi-entscheidbar ist.
Welche der folgenden Aussagen sind korrekt?
- Sei \(L_1\subseteq L_2\) und \(L_2\subseteq L_3\). Sind \(L_1\) und \(L_3\) entscheidbar, dann ist stets auch \(L_2\) entscheidbar.
- Die Vereinigung abzählbar unendlich vieler entscheidbaren Sprachen ist stets entscheidbar.
Sei M eine Turingmaschine über dem Eingabealphabet {a,b} und es gelte für alle \(n\ge0\), dass mindestens \(2^n\) Wörter aus \(\{a,b\}^n\) von M akzeptiert werden.
Was ist keine Voraussetzung für den deterministischen Platzhierarchiesatz (\(s_1,s_2\) Funktionen, es soll \(DSPACE(s_2)\backslash DSPACE(s_1)\neq\emptyset\) gelten)?
Angenommen \(P\neq NP\). Welche der folgenden Aussgen gilt nicht?
Welche der folgendne Aussagen gilt nicht?
Welche Voraussetzung an f ist in Savitchs Theorem \((NSPACE(f)\subseteq DSPACE(f^2))\) gestellt?
Welche Aussage gilt nicht?
Welche der folgenden Komplexitätsklassen ist nicht abgeschlossen gegen Komplement?
Gilt L=P, so gilt auch
Welche der folgendne Aussagen gilt nicht?
Angenommen \(P\neq NP\). Welche der folgenden Probleme ist nicht NP-vollständig?
Angenommen \(P\neq NP\). Welches der folgenden Probleme ist NP-vollständig?
