Berechenbarkeit und Komplexität
Berechenbarkeit und Komplexität für Informatiker
Berechenbarkeit und Komplexität für Informatiker
Welche der folgenden Aussagen gilt nicht?
\(Welche\ der\ folgenden \ Aussagen \ lässt \ sich \ nach \ heutigem \ Wissenstand \ \textit{nicht} \ beantworten? \\\\ a) \ DSPACE(n^3) \subseteq NSPACE(n^5) .\\ b) \ 3-F\ddot{A}RBBARKEIT \in P.\\ c) \ 2-F\ddot{A}RBBARKEIT \in NP .\\ d) \ SAT \in PSPACE \)
c
\( Welche \ der\ folgenden\ Aussagen\ gilt\ \textit{nicht}? \\\\ a) \bigcup_{k \geq 0} NSPACE(n^k) \subseteq \bigcup_{k \geq 0} DSPACE(n^k) .\\ b) Das\ Halteproblem\ für\ Turingmaschinen\ lässt\ sich\ auf\ SAT\ reduzieren. \\ c) Jede\ Sprache\ in\ DTIME(n) \ lässt\ sich\ auf \ SAT\ reduzieren.\\ d) SAT \in PSPACE . \)
b
Sei HALBSAT das Problem, auf Eingabe einer aussagenlogischen Formel F zu entscheiden, ob eine erfüllende Belegung für F existiert, die genau die Hälfte der Variablen in F mit wahr belegt.
Sei INDEPENDENTSET das Problem, auf Eingabe eines ungerichteten Graphen und einer natürlichen Zahl k zu entscheiden, ob es eine unbhängige Menge dieses Graphen der Größe mindestens k gibt. (Eine unabhängige Menge ist eine Knotenmenge M , so dass je zwei Knoten aus M nicht durch eine Kante verbunden sind.) Welche der folgenden Aussagen gilt?
Was besagt der Gödelsche Unvollständigkeitssatz?
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) , so dass \(T(M_w) \) regulär ist.
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) , so dass \(M_w \)auf Eingabe 11 auf allen Berechnungspfaden und auf jedem Band höchstens 42 Zellen besucht.
Welche der folgenden Einschränkungen an die äußere Form von Turingmaschinen (mit mehreren Bändern) stellt eine Einschränkung der durch solche Turingmaschinen akzeptierten Sprachen dar?
Sei f eine beliebige LOOP-berechenbare Funktion. Welche der folgenden Aussagen gilt nicht?
Seien A und B beliebige Sprachen. Welche der folgenden Aussagen gilt nicht?
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) mit \(T(M_w) \neq \emptyset\) .
Sei a die Ackermann-Funktion
Welche Aussage gilt nicht?
\(\underline{\textit{Bekannte NP-vollständige Problem}}\)
- \(SAT\)
- \(3KNF-SAT\)
- \(CLIQUE\)
- \(Gerichteter\ Hamilton\ Kreis\)
- \(Mengenüberdeckung\)
- \(Färbbarkeit\)
- \(Knotenüberdeckung\)
- \(Partition\)
- \(Traveling \ Salesman\)
- \(Bin \ Packing\)
\(\underline{\textit{3KNF-SAT}}\)
gegeben: Eine Boolesche Formel \(F\) in konjunktiver Normalform (Klauselform) mit höchstens 3 Literalen pro Klausel
gefragt: Ist \(F\) erfüllbar?
\(\underline{\textit{Mengenüberdeckung}}\)
gegeben: Ein Mengensystem über einer endlichen Grundmenge \(M\), also \(T_1,...T_k \subseteq M\), sowie eine Zahl \(n \leq k\).
gefragt: Gibt es eine Auswahl aus \(n\) Mengen \(T_{i_1},...,T_{i_n}\), bei der bereits alle Elemente aus \(M\) vorkommen?
\(\underline{\textit{CLIQUE}}\)
gegebe: Ein ungerichteter Graph \(G=(V,E)\)und eine Zahl \(k \in \mathbb{N}\)
gefragt: Besitzt \(G\) eine "Clique" der Größe mindestens \(k\)? (Dies ist eine Teilmenge \(V'\) der Knotenmenge mit \(\vert V' \vert \geq k\) und für alle \(u,v \in V'\) mit \(u \neq v\) gilt: \(\{ u,v \} \in E\)).
\(\underline{\textit{Knotenüberdeckung}}\)
gegeben: Ein ungerichteter Graph \(G=(V,E)\)und eine Zahl \(k \in \mathbb{N}\).
gefragt: Besitzt \(G\) eine "überdeckende Knotenmenge" der Größe höchstens \(k\)? (Dies ist eine Teilmenge \(V' \subseteq V \) mit \(\vert V' \vert \leq k\), so dass für alle Kanten \(\{ u,v \} \in E\) gilt: \(u \in V'\) oder \(v \in V'\)).
\(\underline{\textit{Rucksack (oder SUBSET SUM)}}\)
gegeben: Natürliche Zahlen \(a_1, a_2, ..., a_k \in \mathbb{N}\) und \(b \in \mathbb{N}\).
gefragt: Gibt es eine Teilmenge \(I \subseteq \{ 1,2,..., k\}\) mit \(\sum _{i \in I} a_i = b\)?
\(\underline{\textit{Partition}}\)
gegeben: Natürliche Zahlen \(a_1, a_2,...a_k \in \mathbb{N}\)
gefragt: Gibt es eine Teilmenge \(J \subseteq \{ 1,2,...,k \}\) mit \(\sum_{i \in J} a_i = \sum _{i \notin J} a_i\)?
Was sind Platzschranken?
Eine nichtdeterministische Maschine mit Platzschranke \(f: \mathbb{N} \rightarrow \mathbb{N}\) besitzt keinen Algorithmus, die auf Eingabe der Länge \(n \geq 0\) mehr als \(f(n)\) Felder des Bandes benutzt. Für alle Platzschranken gilt \(f \in \Omega(log(n))\)
Was sind Zeitschranken?
Eine nichtdeterministische Maschine mit Zeitschranke \(f: \mathbb{N} \rightarrow \mathbb{N}\) besitzt keinen Algorithmus, die auf Eingabe der Länge \(n \geq 0\)mehr als \(f(n)\) Rechenschritte machen kann, bevor das Band hält. Es sind auch \(n+1\) Zeitschritte erlaubt, um zu erkennen, wann das Band endet
Welche Platzklassen gibt es?
\(\textbf{DSPACE}(f)\) und \(\textbf{NSPACE}(f)\) für \(f \in \Omega(log(n))\)
Welche Zeitklassen gibt es?
\(\textbf{DTIME}(f) \) und \(\textbf{NTIME}(f) \) für \(f(n) \geq n \ ; \forall n\)
\(\underline{\textbf{DTIME(t)}}\)
\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M\) mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) nach höchstens \(max \{ t(n),n+1 \}\)Schritten hält.
\(\underline{\textbf{NTIME(t)}}\)
\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M\) mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) und bei allen Rechnungen nach höchstens \(max \{ t(n),n+1 \}\)Schritten hält.
\(\underline{\textbf{DSPACE(s)}}\)
\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M \)mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) höchstens \(s(n)\) Arbeitsbandfelder benötigt.
\(\underline{\textbf{NSPACE(s)}}\)
\(L \subseteq \Sigma^*\)| es existiert eine determenistische Turingmaschine \(M \)mit \(L=L(M)\), die auf allen Eingaben der Länge \(n\) bei allen Rechnungen höchstens \(s(n)\) Arbeitsbandfelder benötigt.
\(\underline{\textbf{Beispiele für DSPACE(log(n))}}\)
\( \{ a^nb^nc^n | n \geq 1 \} \\ \{ w\$ w | w \in \Sigma^* \} \)
Die Menge PRIMES mit PRIMES = \(\{ p \in 1 \{ 0,1 \} ^* | \ p \) ist Binärcodierung einer Primzahl
\(\underline{\textbf{Beispiele für Zeitkonstruierbarkeit}}\)
- Polynomfunktionen
- \(f(n)=2^{p(n)}\) und p ist Polynomfunktion
\(\underline{\textbf{Beispiele für Platzkonstruierbarkeit}}\)
\( \lceil log_a^k (n) \rceil , a \geq 2, k \geq 1 \\ \sqrt[5]{n} \)
\(\underline{\textbf{Zusammenhang zeit- und platzkonstruierbar}}\)
\(f \ ist \ zeitkonstruierbar \Rightarrow f \ ist \ platzkonstruierbar\)
\(\underline{\textbf{Satz von Hennie-Stearns }}\)
Sei \(\forall n : f(n) \geq n\) , dann gilt:
\(DTIME(f) \subseteq NTIME(f) \subseteq DSPACE(f) \)
Die Funktion \(f(n)=17n^3-6n^2+3n+23\)ist
Die Funktion \(f(n)=2^{2^n}\) ist
Gebräuchliche Abkürzung für DSPACE, NSPACE, DTIME, NTIME
\(\textbf{L}=\textbf{DSPACE}(log(n)) \\ \textbf{NL}=\textbf{NSPACE}(log(n)) \\ \textbf{P}=\bigcup_{k \geq 1} \textbf{DTIME}(n^k) \\ \textbf{NP}=\bigcup_{k \geq 1} \textbf{NTIME}(n^k) \\ \textbf{PSPACE}=\bigcup_{k \geq 1} \textbf{DSPACE}(n^k) = \bigcup_{k \geq 1} \textbf{NSPACE}(n^k) \)
Welche Varianten algorithmischer Probleme gibt es?
- Entscheidungsvariante
- Berechnungsvariante
- Optimierungsvariante
Grafik Beziehungen wichtiger Komplexitätsklassen
Grafik
\(\underline{\textit{Der Satz von Savitch}}\)
Sei \(s \in \Omega(log(n))\). Dann gilt:
\(\textbf{NSPACE}(s) \subseteq \textbf{DSPACE}(s^2) \)
\(\underline{\textit{Determenistischer Platzhierarchiesatz}}\)
Seien \(s_1, s_2: \mathbb{N} \rightarrow \mathbb{N} \) Funktionen, \(s_1 \notin \Omega (s_2), s_2 \in \Omega(log(n)) \) und \(s_2\) sei platzkonstruierbar. Dann gilt \(\textbf{DSPACE}(s_2) \backslash \textbf{DSPACE}(s_1) \neq \emptyset\) .
Alternativ:
\(\textbf{DSPACE}(f(n)) \subsetneq \textbf{DSPACE}(f(n) \cdot log(f(n)))\)
-
- 1 / 76
-
Lernkarten
Welche der folgenden Aussagen gilt nicht?
\(Welche\ der\ folgenden \ Aussagen \ lässt \ sich \ nach \ heutigem \ Wissenstand \ \textit{nicht} \ beantworten? \\\\ a) \ DSPACE(n^3) \subseteq NSPACE(n^5) .\\ b) \ 3-F\ddot{A}RBBARKEIT \in P.\\ c) \ 2-F\ddot{A}RBBARKEIT \in NP .\\ d) \ SAT \in PSPACE \)
c
\( Welche \ der\ folgenden\ Aussagen\ gilt\ \textit{nicht}? \\\\ a) \bigcup_{k \geq 0} NSPACE(n^k) \subseteq \bigcup_{k \geq 0} DSPACE(n^k) .\\ b) Das\ Halteproblem\ für\ Turingmaschinen\ lässt\ sich\ auf\ SAT\ reduzieren. \\ c) Jede\ Sprache\ in\ DTIME(n) \ lässt\ sich\ auf \ SAT\ reduzieren.\\ d) SAT \in PSPACE . \)
b
Sei HALBSAT das Problem, auf Eingabe einer aussagenlogischen Formel F zu entscheiden, ob eine erfüllende Belegung für F existiert, die genau die Hälfte der Variablen in F mit wahr belegt.
Sei INDEPENDENTSET das Problem, auf Eingabe eines ungerichteten Graphen und einer natürlichen Zahl k zu entscheiden, ob es eine unbhängige Menge dieses Graphen der Größe mindestens k gibt. (Eine unabhängige Menge ist eine Knotenmenge M , so dass je zwei Knoten aus M nicht durch eine Kante verbunden sind.) Welche der folgenden Aussagen gilt?
Was besagt der Gödelsche Unvollständigkeitssatz?
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) , so dass \(T(M_w) \) regulär ist.
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) , so dass \(M_w \)auf Eingabe 11 auf allen Berechnungspfaden und auf jedem Band höchstens 42 Zellen besucht.
Welche der folgenden Einschränkungen an die äußere Form von Turingmaschinen (mit mehreren Bändern) stellt eine Einschränkung der durch solche Turingmaschinen akzeptierten Sprachen dar?
Sei f eine beliebige LOOP-berechenbare Funktion. Welche der folgenden Aussagen gilt nicht?
Seien A und B beliebige Sprachen. Welche der folgenden Aussagen gilt nicht?
Sei L die Sprache aller \(w \in \{ 0,1 \}^*\) mit \(T(M_w) \neq \emptyset\) .
Sei a die Ackermann-Funktion
Welche Aussage gilt nicht?
\(\underline{\textit{Bekannte NP-vollständige Problem}}\)
- \(SAT\)
- \(3KNF-SAT\)
- \(CLIQUE\)
- \(Gerichteter\ Hamilton\ Kreis\)
- \(Mengenüberdeckung\)
- \(Färbbarkeit\)
- \(Knotenüberdeckung\)
- \(Partition\)
- \(Traveling \ Salesman\)
- \(Bin \ Packing\)
\(\underline{\textit{3KNF-SAT}}\)
gegeben: Eine Boolesche Formel \(F\) in konjunktiver Normalform (Klauselform) mit höchstens 3 Literalen pro Klausel
gefragt: Ist \(F\) erfüllbar?
\(\underline{\textit{Mengenüberdeckung}}\)
gegeben: Ein Mengensystem über einer endlichen Grundmenge \(M\), also \(T_1,...T_k \subseteq M\), sowie eine Zahl \(n \leq k\).
gefragt: Gibt es eine Auswahl aus \(n\) Mengen \(T_{i_1},...,T_{i_n}\), bei der bereits alle Elemente aus \(M\) vorkommen?
\(\underline{\textit{CLIQUE}}\)
gegebe: Ein ungerichteter Graph \(G=(V,E)\)und eine Zahl \(k \in \mathbb{N}\)
gefragt: Besitzt \(G\) eine "Clique" der Größe mindestens \(k\)? (Dies ist eine Teilmenge \(V'\) der Knotenmenge mit \(\vert V' \vert \geq k\) und für alle \(u,v \in V'\) mit \(u \neq v\) gilt: \(\{ u,v \} \in E\)).
\(\underline{\textit{Knotenüberdeckung}}\)
gegeben: Ein ungerichteter Graph \(G=(V,E)\)und eine Zahl \(k \in \mathbb{N}\).
gefragt: Besitzt \(G\) eine "überdeckende Knotenmenge" der Größe höchstens \(k\)? (Dies ist eine Teilmenge \(V' \subseteq V \) mit \(\vert V' \vert \leq k\), so dass für alle Kanten \(\{ u,v \} \in E\) gilt: \(u \in V'\) oder \(v \in V'\)).
\(\underline{\textit{Rucksack (oder SUBSET SUM)}}\)
gegeben: Natürliche Zahlen \(a_1, a_2, ..., a_k \in \mathbb{N}\) und \(b \in \mathbb{N}\).
gefragt: Gibt es eine Teilmenge \(I \subseteq \{ 1,2,..., k\}\) mit \(\sum _{i \in I} a_i = b\)?
\(\underline{\textit{Partition}}\)
gegeben: Natürliche Zahlen \(a_1, a_2,...a_k \in \mathbb{N}\)
gefragt: Gibt es eine Teilmenge \(J \subseteq \{ 1,2,...,k \}\) mit \(\sum_{i \in J} a_i = \sum _{i \notin J} a_i\)?
