# HG changeset patch # User Markus Kaiser # Date 1373925115 -7200 # Node ID a2d28c18251a2e9d3630191f0528a5f5917d7cf8 # Parent d5aa58bee83b762fcd5355273514aca579f61e6e ue12 notes diff -r d5aa58bee83b -r a2d28c18251a notes/tex/complete_notes.tex --- 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} diff -r d5aa58bee83b -r a2d28c18251a notes/tex/computation.tex --- 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} +} diff -r d5aa58bee83b -r a2d28c18251a notes/tex/ue12_notes.tex --- /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}