Berechenbarkeit und Komplexität

• \(SAT\)
• \(3KNF-SAT\)
• \(CLIQUE\)
• \(Gerichteter\ Hamilton\ Kreis\)
• \(Mengenüberdeckung\)
• \(Färbbarkeit\)
• \(Knotenüberdeckung\)
• \(Partition\)
• \(Traveling \ Salesman\)
• \(Bin \ Packing\)

gegeben: Eine Boolesche Formel \(F\) in konjunktiver Normalform (Klauselform) mit höchstens 3 Literalen pro Klausel

gefragt: Ist \(F\) erfüllbar?

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?

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

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

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

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

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

\(\textbf{DSPACE}(f)\) und \(\textbf{NSPACE}(f)\) für \(f \in \Omega(log(n))\)

\(\textbf{DTIME}(f) \) und \(\textbf{NTIME}(f) \) für \(f(n) \geq n \ ; \forall n\)

\(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. 

\(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. 

\(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.

\(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.

\( \{ 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

• Polynomfunktionen 
• \(f(n)=2^{p(n)}\) und p ist Polynomfunktion

\( \lceil log_a^k (n) \rceil , a \geq 2, k \geq 1 \\ \sqrt[5]{n} \)

\(f \ ist \ zeitkonstruierbar \Rightarrow f \ ist \ platzkonstruierbar\)

Sei \(\forall n : f(n) \geq n\) , dann gilt: 

\(DTIME(f) \subseteq NTIME(f) \subseteq DSPACE(f) \)