--- a/notes/tex/complete_notes.tex	Mon Jul 15 23:51:34 2013 +0200
+++ b/notes/tex/complete_notes.tex	Mon Jul 15 23:51:55 2013 +0200
@@ -87,4 +87,14 @@
 \showUnit{rice}
 \showUnit{pcp}
 \showUnit{pcpbeispiel}
+
+% ue12
+\showUnit{time}
+\showUnit{ntime}
+\showUnit{pundnp}
+\showUnit{verifikator}
+\showUnit{preduktion}
+\showUnit{npvollstaendigkeit}
+\showUnit{sat}
+\showUnit{3col}
 \end{document}

--- a/notes/tex/computation.tex	Mon Jul 15 23:51:34 2013 +0200
+++ b/notes/tex/computation.tex	Mon Jul 15 23:51:55 2013 +0200
@@ -728,3 +728,204 @@
     \end{center}
 \end{frame}
 }
+
+\defineUnit{time}{%
+\begin{frame}[t]
+    \frametitle{$TIME$}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[$TIME$]
+        Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{DTM} $M$ mit Eingabe $w$ hält als $\alert{time_M(w)} \in \N \cup \left\{ \infty \right\}$.\\
+        \vspace{1em}
+        Sei $f : \N \to \N$ total. Dann ist
+        \begin{align*}
+            \alert{TIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{DTM}\  M. A = L(M) \wedge \\
+        &\forall w \in \Sigma^*. \structure{time_M(w) \leq f(|w|)} \}
+        \end{align*}
+        die Klasse der \structure{in Zeit $f(n)$} von einer \structure{DTM} entscheidbaren Sprachen.
+    \end{definition}
+
+    \vfill
+
+    \begin{itemize}
+        \item $TIME(\Oh(n))$ enthält alle "\structure{linearen Probleme}".
+        \item Also alle Probleme, für die ein Linearzeitalgorithmus existiert.
+    \end{itemize}
+\end{frame}
+}
+
+\defineUnit{ntime}{%
+\begin{frame}[t]
+    \frametitle{$NTIME$}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[$NTIME$]
+        Wir bezeichnen die minimale Anzahl der Schritte, bis eine \structure{NTM} $M$ mit Eingabe $w$ hält als $\alert{ntime_M(w)} \in \N$. 
+        \[ \alert{ntime_M(w)} := \begin{cases} \text{minimale Schrittanzahl} & \text{falls } w \in L(M) \\ 0 & \text{falls } w \not \in L(M)\end{cases} \]
+        Dann ist
+        \begin{align*}
+            \alert{NTIME(f(n))} := \{ A \subseteq \Sigma^* \mid \exists &\structure{NTM}\  M. A = L(M) \wedge \\
+        &\forall w \in \Sigma^*. \structure{ntime_M(w) \leq f(|w|)} \}
+        \end{align*}
+        die Klasse der \structure{in Zeit $f(n)$} von einer \structure{NTM} entscheidbaren Sprachen.
+    \end{definition}
+\end{frame}
+}
+
+\defineUnit{pundnp}{%
+\begin{frame}
+    \frametitle{P und NP}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}
+        \alert{P} ist die Menge aller von einer \structure{DTM} in polynomieller Zeit entscheidbaren Sprachen.
+        \[\alert{P}:= \bigcup_{p\text{ Polynom}} TIME(p(n)) = \bigcup_{k \in \N} TIME(\alert{\Oh(n^k)}) \]
+    \end{definition}
+
+    \begin{definition}
+        \alert{NP} ist die Menge aller von einer \structure{NTM} in polynomieller Zeit entscheidbaren Sprachen.
+        \[\alert{NP}:= \bigcup_{p\text{ Polynom}} NTIME(p(n)) = \bigcup_{k \in \N} NTIME(\alert{\Oh(n^k)}) \]
+    \end{definition}
+\end{frame}
+}
+
+\defineUnit{verifikator}{%
+\begin{frame}
+    \frametitle{Verifikator}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Verifikator]
+        Sei $M$ eine \structure{DTM} mit $L(M) \subseteq \left\{ w\# c \mid w \in \Sigma^*, c \in \Delta^* \right\}$.
+        \begin{itemize}
+            \item Falls $w\#c \in L(M)$, dann heißt $c$ \alert{Zertifikat} für $w$.
+            \item $M$ ist ein \alert{polynomiell beschränkter Verifikator} für
+                \[\left\{ \structure{w \in \Sigma^*} \mid \exists c \in \Delta^* . w\#c \in L(M) \right\}\]
+                falls $time_M(w\#c) \leq p(|w|)$ für ein Polynom $p$.
+        \end{itemize}
+    \end{definition}
+
+    \begin{itemize}
+        \item \structure{NTM} rät Lösung (Zertifikat), \structure{DTM} probiert sie aus.
+        \item Verifizieren (wahrscheinlich) einfacher als Lösung finden.
+    \end{itemize}
+
+    \vfill
+
+    \begin{theorem}
+        \alert{$A \in NP$} gdw es einen pol. beschränkten Verifikator für A gibt.
+    \end{theorem}
+\end{frame}
+}
+
+\defineUnit{preduktion}{%
+\begin{frame}
+    \frametitle{Polynomielle Reduzierbarkeit}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Polynomielle Reduzierbarkeit]
+        Eine Menge $A \subseteq \Sigma^*$ ist \alert{polynomiell reduzierbar} auf eine Menge $B \subseteq \Gamma^*$ gdw es eine totale und \structure{von einer DTM in polynomieller Zeit} berechenbare Funktion $f:\Sigma^* \to \Gamma^*$ gibt mit
+        \[\forall w \in \Sigma^*. w \in A \Longleftrightarrow f(w) \in B\]
+        Wir schreiben dann \alert{$A \leq_P B$}.
+    \end{definition}
+
+    \vfill
+
+    \begin{itemize}
+        \item Die Relation $\leq_P$ ist \structure{transitiv}.
+        \item P und NP sind \structure{nach unten abgeschlossen}:
+            \[A \leq_P B \in P/NP \Longrightarrow A \in P/NP\]
+    \end{itemize}
+\end{frame}
+}
+
+\defineUnit{npvollstaendigkeit}{%
+\begin{frame}
+    \frametitle{NP-Vollständigkeit}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[NP-Schwere]
+        Eine Sprache $L$ heißt \alert{NP-schwer} (NP-hart) wenn sich \structure{alle Sprachen} in NP auf $L$ reduzieren lassen.
+        \[\forall A \in NP. A \leq_P L\]
+    \end{definition}
+
+    \begin{definition}[NP-Vollständigkeit]
+        Eine Sprache $L$ heißt \alert{NP-vollständig} wenn $L$ \structure{NP-schwer} ist und \structure{$L \in NP$}.
+    \end{definition}
+
+    \vfill
+
+    \structure{Fragen}:
+    \begin{itemize}
+        \item Gibt es überhaupt NP-vollständige Sprachen?
+        \item Gibt es eine NP-vollständige Sprache in $P$?
+    \end{itemize}
+\end{frame}
+}
+
+\defineUnit{sat}{%
+\begin{frame}
+    \frametitle{SAT}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Aussagenlogik]
+        Syntax der \alert{Aussagenlogik}.\\
+        \begin{description}
+            \item[Formeln] $F \rightarrow \neg F \mid (F \wedge F) \mid (F \vee F) \mid X$
+            \item[Variablen] $X \rightarrow x \mid y \mid z \mid \ldots$
+        \end{description}
+    \end{definition}
+
+    \vfill
+
+    \begin{definition}[SAT]
+        Gegeben eine \structure{aussagenlogische Formel} $F$.\\
+        Ist $F$ \alert{erfüllbar}, also gibt es eine Belegung der Variablen in $F$, sodass $F$ gilt?
+    \end{definition}
+
+    \begin{theorem}[Cook 1971]
+        $\mathbf{SAT}$ ist \alert{NP-vollständig}.
+    \end{theorem}
+\end{frame}
+}
+
+\defineUnit{3col}{%
+\begin{frame}
+    \frametitle{3COL}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[3COL]
+        Gegeben ein \structure{Graph} $G = (V, E)$.\\
+        Gibt es eine \alert{Färbung der Knoten} $V$ mit $3$ Farben, so dass keine zwei benachbarten Knoten die gleiche Farbe haben?
+    \end{definition}
+
+    \vfill
+
+    \begin{center}
+        \begin{tikzpicture}
+            \tikzstyle{red} = [fill=tumred!50]
+            \tikzstyle{green} = [fill=tumgreen!50]
+            \tikzstyle{blue} = [fill=tumblue!50]
+            \tikzstyle{vertex} = [draw, circle, thin, blue]
+            \tikzstyle{edge} = [draw, thick]
+
+            \foreach \name/\angle/\dist/\col in {
+                ia/18/0.8cm/blue, ib/90/0.8cm/red, ic/162/0.8cm/red, id/234/0.8cm/green, ie/306/0.8cm/green,
+                oa/18/1.6cm/red, ob/90/1.6cm/blue, oc/162/1.6cm/green, od/234/1.6cm/red, oe/306/1.6cm/blue} {
+                \node<1>[vertex] (\name) at (\angle:\dist) {};
+                \node<2>[vertex, \col] (\name) at (\angle:\dist) {};
+            }
+
+            \foreach \a/\b in {
+                ia/oa, ib/ob, ic/oc, id/od, ie/oe,
+                oa/ob, ob/oc, oc/od, od/oe, oe/oa,
+                ia/ic, ic/ie, ie/ib, ib/id, id/ia} {
+                \draw[edge] (\a) -- (\b);
+            }
+        \end{tikzpicture}
+    \end{center}
+
+    \begin{theorem}
+        Es ist \alert{$\mathbf{3COL} \leq_P \mathbf{SAT}$} und $\alert{\mathbf{SAT}} \leq_P \mathbf{3SAT} \alert{\leq_P \mathbf{3COL}}$.
+    \end{theorem}
+\end{frame}
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue12_notes.tex	Mon Jul 15 23:51:55 2013 +0200
@@ -0,0 +1,18 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 12: Komplexitätstheorie}
+\subtitle{Theoretische Informatik Sommersemester 2013}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{time}
+\showUnit{ntime}
+\showUnit{pundnp}
+\showUnit{verifikator}
+\showUnit{preduktion}
+\showUnit{npvollstaendigkeit}
+\showUnit{sat}
+\showUnit{3col}
+\end{document}