\documentclass[a4paper, 12pt]{article}

% Deutsch
% \usepackage{ngerman}
% \usepackage[ansinew]{inputenc}
% \usepackage[T1]{fontenc}
% \usepackage{lmodern}
\usepackage[main=ngerman,british]{babel}

% Sonderzeichen
% \usepackage{bbold}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{mathtools}
\usepackage{linearA}
\usepackage{emoji}
\setemojifont{Segoe UI Emoji}

% Zeilenumbruch
\usepackage{breqn}

% Brüche
\usepackage{xfrac}
% \newcommand\sfrac[2]{#1/#2}

% Aufzählungen
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{multicol}

% Farbe
\usepackage[dvipsnames]{xcolor}
\definecolor{darkgray}{gray}{0.3}
\usepackage{colortbl}

% Tabellen
\usepackage{array}
\newcommand{\PreserveBackslash}[1]{\let\temp=\\#1\let\\=\temp}
\newcolumntype{C}[1]{>{\PreserveBackslash\centering}p{#1}}
\newcolumntype{R}[1]{>{\PreserveBackslash\raggedleft}p{#1}}
\newcolumntype{L}[1]{>{\PreserveBackslash\raggedright}p{#1}}

% Footer / Header
\usepackage{fancyhdr}
\usepackage{lastpage}

% Für den Header
\usepackage[strict]{changepage}

% Seitenlayout und -stil
\usepackage[a4paper,top=15mm,bottom=25mm,left=25mm, right=25mm]{geometry}
\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0.0pt}
\cfoot{(Seite \thepage \hspace{1pt} von \pageref{LastPage})}
\usepackage{adjustbox}

% zum Testen
% \overfullrule=2cm
\usepackage{lipsum}

\usepackage{graphicx}
\usepackage{tikz}
% \usetikzlibrary{calc,decorations.pathreplacing,shapes.geometric,arrows.meta}
\usetikzlibrary{calc,decorations.pathreplacing,shapes,arrows.meta,bending}
\usepackage{rotating}
\usepackage{caption}
\usepackage{subcaption}
\renewcommand{\figurename}{\footnotesize Abb.}

% Algorithmen
\usepackage{algorithm, comment}
\usepackage{algpseudocode}
\usepackage{listings}
\usepackage{lstautogobble}

% Sprachen
\lstdefinelanguage{goto}
	{morekeywords={GOTO,IF,THEN,HALT},
	sensitive=false,
	morecomment=[l]{//},
	morecomment=[s]{/*}{*/},
	morestring=[b]",
	moredelim=[is][\color{olive}]{@}{@},
	keywordstyle=\color{teal},
	commentstyle={\ttfamily\color{darkgray}},
	tabsize=2,
	basicstyle=\ttfamily
}
\lstdefinelanguage{pseudo}
	{morekeywords={function,if,then,else,fi,for,to,step,do,od,end,while,repeat,until,foreach,return},
	sensitive=false,
	morecomment=[l]{//},
	morecomment=[s]{/*}{*/},
	morestring=[b]",
	moredelim=[is][\color{olive}]{@}{@},
	keywordstyle=\bfseries\color{teal},
	commentstyle={\ttfamily\color{darkgray}},
	tabsize=2,
	basicstyle=\ttfamily,
	mathescape=true,
	numbers=left,
	numbersep=5pt,
	numberstyle=\small\color{darkgray},
	frame=leftline,
	rulecolor=\color{darkgray}
}

% foreach
\algnewcommand\algorithmicforeach{\textbf{foreach}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}

% loop
\algrenewcommand\algorithmicloop{\textbf{loop}}
\algdef{S}[WHILE]{LoopX}[1]{\algorithmicloop\ #1\ \algorithmicdo}
\newcommand{\EndLoopX}{\algrenewtext{EndWhile}{{\newalgstyle end}}\EndWhile\algrenewtext{EndWhile}{{\newalgstyle od}}}

% custom keywords
\newcommand{\key}[1]{{\ttfamily\bfseries\color{teal}#1}}
\newcommand{\Input}[1]{\Statex\key{Input:} {#1}}

% full line comment
\newcommand{\linecomment}[1]{\Statex{\color{darkgray}$\triangleright$ #1}}

% algorithmic-Anpassungen
\algrenewcommand\algorithmiccomment[1]{{\color{darkgray}\hfill$\triangleright$ #1}}
\newcommand\newalgstyle{\ttfamily\bfseries\color{teal}}
\algrenewcommand\algorithmicend{{\newalgstyle end}}
\algrenewcommand\algorithmicdo{{\newalgstyle do}}
\algrenewcommand\algorithmicwhile{{\newalgstyle while}}
\algrenewcommand\algorithmicfor{{\newalgstyle for}}
\algrenewcommand\algorithmicforall{{\newalgstyle for all}}
\algrenewcommand\algorithmicforeach{{\newalgstyle for each}}
\algrenewcommand\algorithmicloop{{\newalgstyle loop}}
\algrenewcommand\algorithmicrepeat{{\newalgstyle repeat}}
\algrenewcommand\algorithmicuntil{{\newalgstyle until}}
\algrenewcommand\algorithmicprocedure{{\newalgstyle procedure}}
\algrenewcommand\algorithmicfunction{{\newalgstyle function}}
\algrenewcommand\algorithmicif{{\newalgstyle if}}
\algrenewcommand\algorithmicthen{{\newalgstyle then}}
\algrenewcommand\algorithmicelse{{\newalgstyle else}}
\algrenewcommand\algorithmicrequire{{\newalgstyle Require:}}
\algrenewcommand\algorithmicensure{{\newalgstyle Ensure:}}
\algrenewcommand\algorithmicreturn{{\newalgstyle return}}
\algrenewtext{EndWhile}{{\newalgstyle od}}
\algrenewtext{EndFor}{{\newalgstyle od}}
\algrenewtext{EndLoop}{{\newalgstyle od}}
\algrenewtext{EndIf}{{\newalgstyle fi}}
\algrenewtext{EndFunction}{{\newalgstyle end}}

% kleine Aufzählungszeichen & Prozent
% \renewcommand{\labelitemi}{\raise .5ex\hbox{\tiny$\bullet$}}
\renewcommand\labelitemi{$\vcenter{\hbox{\tiny$\bullet$}}$}
% \renewcommand{\labelitemi}{\boldmath$\cdot$}
\newcommand{\pct}{\,\scalebox{.9}{\%} }

% \Item-Befehl, damit Align-Umgebungen in der richtigen Zeile beginnen
\newcommand\Item[1][]{%
  \ifx\relax#1\relax  \item \else \item[#1] \fi
  \abovedisplayskip=0pt\abovedisplayshortskip=0pt~\vspace*{-\baselineskip}
}

% Damit man Anführungszeichen hübscher schreiben kann als "`"'
\newcommand{\enquote}[1]{``{#1}''}

% für die Kurzschreibweisen
\usepackage{xspace}

% Kurzschreibweisen
\newcommand{\setN}{\mathbb{N}}
\newcommand{\setZ}{\mathbb{Z}}
\newcommand{\setQ}{\mathbb{Q}}
\newcommand{\setR}{\mathbb{R}}
\newcommand{\setP}{\mathbb{P}}
\newcommand{\sigStar}{\Sigma^{*}}
\newcommand{\EStar}{E^{*}}
\newcommand{\binStar}{\{0,1\}^{*}}
\newcommand{\Oh}[1]{\mathcal{O}({#1})}
\newcommand{\OhOmega}[1]{\Omega({#1})}
\newcommand{\OhTheta}[1]{\Theta({#1})}
\newcommand{\qed}{\hfill $\square$}
\newcommand{\Null}{\textsc{Null}\xspace}
\newcommand{\overbar}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}
\newcommand{\True}{\textsc{True}\xspace}
\newcommand{\False}{\textsc{False}\xspace}
\newcommand{\defeq}{\vcentcolon=} % := (benötigt mathtools)
\newcommand{\eqdef}{=\vcentcolon} % =: (benötigt mathtools)
\newcommand{\Hinweis}[1]{\smallskip\noindent(\emph{Hinweis:} {#1})}
\newcommand{\Bemerkung}[1]{\smallskip\noindent(\emph{Bemerkung:} {#1})}
\newcommand{\ztm}[2]{\begin{array}{c} {#1} \\ {#2} \end{array}}
\newcommand{\classL}{\textsf{L}\xspace}
\newcommand{\classNL}{\textsf{NL}\xspace}
\newcommand{\classP}{\textsf{P}\xspace}
\newcommand{\classNP}{\textsf{NP}\xspace}
\newcommand{\classPSPACE}{\textsf{PSPACE}\xspace}
\newcommand{\classNPSPACE}{\textsf{NPSPACE}\xspace}
\newcommand{\classEXP}{\textsf{EXP}\xspace}

% Gaußklammern
\providecommand{\floor}[1]{\left \lfloor #1 \right \rfloor }
\providecommand{\ceil}[1]{\left \lceil #1 \right \rceil }

% Mathekommentare
\newcommand{\mathcomm}[1]{\triangleright~\text{#1}}
% Farbig unterstreichen
\def\mathunderline#1#2{\color{#1}\underline{{\color{black}#2}}\color{black}}

% Silbentrennung
\hyphenation{While-Schlei-fe}
\hyphenation{While-be-rech-en-bar}

% Mayaziffern
\usepackage{fontspec}
\newfontface{\babm}{BabelStone Mayan Numerals}
\DeclareRobustCommand\mzero{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E0}}}%
}
\DeclareRobustCommand\mone{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E1}}}%
}
\DeclareRobustCommand\mtwo{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E2}}}%
}
\DeclareRobustCommand\mthree{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E3}}}%
}
\DeclareRobustCommand\mfour{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E4}}}%
}
\DeclareRobustCommand\mfive{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E5}}}%
}
\DeclareRobustCommand\msix{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E6}}}%
}
\DeclareRobustCommand\mseven{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E7}}}%
}
\DeclareRobustCommand\meight{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E8}}}%
}
\DeclareRobustCommand\mnine{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E9}}}%
}
\DeclareRobustCommand\mten{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EA}}}%
}
\DeclareRobustCommand\meleven{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EB}}}%
}
\DeclareRobustCommand\mtwelve{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EC}}}%
}
\DeclareRobustCommand\mthirteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2ED}}}%
}
\DeclareRobustCommand\mfourteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EE}}}%
}
\DeclareRobustCommand\mfifteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EF}}}%
}
\DeclareRobustCommand\msixteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F0}}}%
}
\DeclareRobustCommand\mseventeen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F1}}}%
}
\DeclareRobustCommand\meighteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F2}}}%
}
\DeclareRobustCommand\mnineteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F3}}}%
}

% Counter für Aufgaben
\newcounter{AufgabenNummer}
\setcounter{AufgabenNummer}{1}

% Counter für Lösungen
\newcounter{LoesungNummer}
\setcounter{LoesungNummer}{1}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ÄNDERN
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Variablen für Übungsnummer und Abgabedatum
\newcommand\Nummer{9}
\newcommand\Abgabe{28.\,Januar 2022 um 12 Uhr}
\newif\ifhideloesung
\usepackage{substr}
\IfSubStringInString{\detokenize{loesung}}{\jobname}{}{\hideloesungtrue}
% \hideloesungtrue % Nicht kommentiert = Lösungen versteckt

% Environment für Aufgaben
\newenvironment{aufgabe}[1]{\noindent \textbf{Aufgabe \Nummer{}.\arabic{AufgabenNummer}} \textit{(#1 Punkte)} \nopagebreak \smallskip \par \noindent \ignorespaces}{\stepcounter{AufgabenNummer} \bigskip}

% Environment für Lösungen
\newenvironment{loesung}{\color{blue} \noindent \textbf{Lösung} \nopagebreak \smallskip \par \noindent \ignorespaces}{\bigskip}

% Environment für Lösungen 2
\newenvironment{loesung2}{\color{blue} \noindent \textbf{Lösung \Nummer{}.\arabic{LoesungNummer}} \nopagebreak \smallskip \par \noindent \ignorespaces}{\stepcounter{LoesungNummer} \bigskip}

% Environment für Ankündigungen
\newenvironment{ankuendigung}{\noindent \hrulefill \medskip \par \noindent \textbf{Ankündigung:} }{\par \noindent \hrulefill \bigskip}

% Environment für Mitteilung
\newenvironment{mitteilung}{\noindent \hrulefill \medskip \par \noindent \textbf{Mitteilung:} }{\par \noindent \hrulefill \bigskip}

% Environment für Definitionen
\newenvironment{definition2}{\noindent \textbf{Definition(en)} \smallskip \par \noindent \ignorespaces}{\bigskip}

% Environment für Dateinamensschema
% \newenvironment{dateinamensschema}{\noindent \hrulefill \medskip \par \noindent \textbf{Bitte beachten Sie die folgenden Vorgaben für die Abgabe:}}{\par \noindent \hrulefill \bigskip}
\newenvironment{dateinamensschema}{\noindent \hrulefill \medskip \par \noindent \textbf{Bitte beachten Sie die folgenden Vorgaben für die Abgabe:}}{\par \noindent \hrulefill \pagebreak}

% Kopfzeile
\newcommand{\Kopfzeile}{
\begin{center}
	\noindent
	\parbox[t][5em][c]{0.5\textwidth}{
	\begin{flushleft}
		\textmd{Datenstrukturen und Effiziente Algorithmen} \\
		\textit{Fachbereich IV - Informatik} \\
		\textit{Universität Trier}
	\end{flushleft}}
	\hfill
	\parbox[t][5em][c]{0.49\textwidth}{
	\begin{flushright}
		Moritz Gobbert \\
		\textit{gobbert@uni-trier.de} \\
		\textit{Raum H\,428}
	\end{flushright}}
\end{center}
\bigskip
}

% Titel
\newcommand{\Titel}{
\begin{center}
	{\Large Berechenbarkeit und Komplexitätstheorie} \\
	Wintersemester 2021/2022 \\
	Aufgabenblatt \Nummer \\
	\textbf{Abgabe: \Abgabe}
\end{center}
}

\ifhideloesung
	\usepackage{environ}
	\NewEnviron{hide}{}
	\let\loesung\hide
	\let\endloesung\endhide
\else
	\usepackage{environ}
	\NewEnviron{hide}{}
	\let\dateinamensschema\hide
	\let\enddateinamensschema\endhide
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                               Textanfang                                                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
	\Titel
	\bigskip
	\begin{dateinamensschema}
		Geben Sie nur eine \emph{einzelne} Datei ab. Diese Datei sollte vorzugsweise im \texttt{pdf}-Format sein. Falls Ihre Abgabe aus mehr als einer Datei besteht, dann packen Sie diese bitte zusammen in ein \texttt{zip}-Archiv. Notieren Sie auf Ihrer Abgabe die Namen und Matrikelnummern aller an der Abgabe beteiligten Personen. Achten Sie darauf, dass Ihre Datei leserlich ist -- insbesondere bei Fotos einer handschriftlichen Abgabe. Bezeichnen Sie die abzugebende Datei nach dem folgenden Muster:
		
		\begin{center}\texttt{Nachname\_Vorname\_Matrikelnummer.pdf} (bzw.\ \texttt{.zip})\end{center}
		
		\noindent{}Falls Sie als Gruppe abgeben reichen als Dateiname die Daten eines Gruppenmitglieds -- die Daten der anderen Mitglieder stehen in der Lösung selbst. Zur Abgabe gibt es in \emph{Moodle} einen passenden Abschnitt namens \enquote{\texttt{Übung \Nummer}} in dem Sie Ihre Lösungen hochladen können.
		
		Abgabetermin ist Freitag, der \textbf{\Abgabe}.
	\end{dateinamensschema}
	
	\begin{definition2}
		\small
		\begin{itemize}
			\item Eine \emph{Clique} in einem ungerichteten Graphen $G = (V,E)$ ist eine Menge von Knoten $V' \subseteq V$, die paarweise benachbart sind. Für alle $u,v \in V'$ (mit $u \neq v$) gilt also $uv \in E$. Als \emph{Größe} der Clique bezeichnen wir die Anzahl der Knoten $|V'|$.
			\item \underline{\textsc{$k$-Clique}} (für $k \in \setN$):
				\begin{itemize}
					\item \textbf{gegeben:} Ein ungerichteter Graph $G = (V, E)$
					\item \textbf{gefragt:} Hat $G$ eine Clique der Größe $k$?
				\end{itemize}
			\item \underline{\textsc{Clique}}:
				\begin{itemize}
					\item \textbf{gegeben:} Ein ungerichteter Graph $G = (V, E)$ und eine Zahl $k \in \setN$
					\item \textbf{gefragt:} Hat $G$ eine Clique der Größe $k$?
				\end{itemize}
			\item \underline{\textsc{$2$-Sat}}:
				\begin{itemize}
					\item \textbf{gegeben:} Ein Boolesche Formel $\mathcal{F}$ in konjunktiver Normalform mit genau 2 Literalen pro Klausel (d.\,h.\ $\mathcal{F}$ ist von der Form $(\ell_{1,1} \vee \ell_{1,2}) \wedge (\ell_{2,1} \vee \ell_{2,2}) \dots \wedge (\ell_{m,1} \vee \ell_{m,2})$, wobei $\ell_{i,j} \in \{x_1, \dots, x_n, \neg x_1, \dots, \neg x_n\}$).
					\item \textbf{gefragt:} Hat $\mathcal{F}$ eine erfüllende Belegung?
				\end{itemize}
			\item \underline{\textsc{Färbbarkeit}}:
				\begin{itemize}
					\item \textbf{gegeben:} Ein ungerichteter Graph $G = (V, E)$ und eine Zahl $k \in \setN$
					\item \textbf{gefragt:} Gibt es eine Funktion $f \colon V \rightarrow \{1, \dots, k\}$, sodass für alle $v,u \in V$ (mit $vu \in E$) gilt: $f(v) \neq f(u)$?
					
					(Anders ausgedrückt: Kann man die Knoten des Graphen so färben, dass keine benachbarten Knoten dieselbe Farbe haben?)
				\end{itemize}
		\end{itemize}
	\end{definition2}
	\pagebreak
	
	\begin{aufgabe}{2 + 2 + 2}
		\begin{enumerate}[\quad a)]
			\item Zeichnen Sie einen Graphen mit genau $5$ Knoten, der eine $3$-Clique, aber keine $4$-Clique enthält.
			\item Zeigen Sie: $\textsc{$k$-Clique} \in \classP$. (\emph{Hinweis:} $k$ ist Teil der Problemdefinition.)
			\item Zeigen Sie: $\textsc{Clique} \in \classNP$. (\emph{Hinweis:} $k$ ist Teil der Eingabe.)
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item Hier könnte man einen $K_3$ zeichnen um die $3$-Clique abzudecken. Wenn man dann noch zwei weitere Knoten hinzufügt, dann hat der Graph insgesamt $5$ Knoten, aber keine $4$-Clique. Formal also $G = (\{a, b, c, d, e\},$ $\{ab, ac, bc\})$
			\begin{figure}[h!]
				\centering
				\begin{tikzpicture}
					[nodedot/.style={draw,fill=blue,shape=circle,minimum size=.2cm,inner sep=0},
					nodelabel/.style={blue}]
					% nodes
					\node [nodedot] (a) at (0, 0) {};
					\node [nodelabel,anchor=east] at (a.west) {$a$};
					\node [nodedot] (b) at (0, 1) {};
					\node [nodelabel,anchor=east] at (b.west) {$b$};
					\node [nodedot] (c) at (1, 1) {};
					\node [nodelabel,anchor=south] at (c.north) {$c$};
					\node [nodedot] (d) at (2, 1) {};
					\node [nodelabel,anchor=west] at (d.east) {$d$};
					\node [nodedot] (e) at (2, 0) {};
					\node [nodelabel,anchor=west] at (e.east) {$e$};
					% edges
					\draw (a) -- (b);
					\draw (a) -- (c);
					\draw (b) -- (c);
				\end{tikzpicture}
			\end{figure}
			\item Sei $G = (V(G), E(G))$ ein Graph mit $|V(G)| = n$. Sei weiter $H$ ein Teilgraph von $G$, also $V(H) \subseteq V(G)$ und $E(H) = E(G) \cap (V(H) \times V(H))$. (Man nimmt also einen Teil der Knoten aus $G$ weg und streicht die Kanten, die zu den wegfallenden Knoten gehören.) Nun gilt:
			
			\noindent $G$ hat eine Clique der Größe $k$ $\Leftrightarrow \exists$ \emph{vollständiger} Teilgraph $H$ von $G$ mit $|V(H)| = k$.
			
			\noindent Weiter lässt sich in Polynomzeit prüfen, ob ein Graph (hier $H$) vollständig ist: Es gibt höchstens $|V(H)|^2 = k^2$ viele Kanten, die man prüfen muss.
			
			\noindent Außerdem enthält $G$ höchstens $n \choose k$ $\leq n^k$ viele $k$-\enquote{knotige} Teilgraphen.
			
			\noindent Wenn man nun für alle $k$-knotigen Teilgraphen überprüft, ob diese vollständig sind, dann ergibt sich eine Laufzeit von $\mathcal{O}(n^k \cdot k^2)$ und da $k$ Teil der Problemdefinition und somit konstant ist, ist diese Laufzeit polynomiell.
			\item Der folgende nicht-deterministische Algorithmus findet eine Clique der Größe $k$ in einem Graphen:
			
			\begin{itemize}
				\item Falls $k > |V|$, lehne ab.
				\item Rate Knotenmenge $X \subseteq V$ mit $|X| = k$.
				\item Teste für alle $u, v \in X$ mit $u \neq v$, ob $uv \in E$.
			\end{itemize}
			
			Die ersten beiden Schritte haben (je nach Definition) konstante oder höchstens lineare Laufzeit. Der dritte Schritt hat eine quadratische Laufzeit, da es höchstens $|X|^2 \leq |V|^2$ viele Knotenpaare gibt, die getestet werden müssen. Zusammen ergibt sich also eine polynomielle Laufzeit für den nicht-deterministischen Algorithmus.
		\end{enumerate}
	\end{loesung}
	
	\begin{aufgabe}{5}
		Zeigen Sie: $\textsc{$2$-Sat} \in \classP$. (Es ist kein formaler Beweis gefordert. Es reicht, wenn Sie Ihre Überlegungen kurz skizzieren.)
		
		\Hinweis{Formen Sie die Klauseln zu je zwei Implikation und. Überlegen Sie sich, was es für diese Implikationen bedeutet, wenn jeweils eines der beiden Literale auf \emph{wahr} gesetzt wird und wie Sie diese Abhängigkeit in einem Graph darstellen können.}
	\end{aufgabe}
	
	\begin{loesung}
		Bei \textsc{$2$-Sat} nutzt man aus, dass jede Klausel genau $2$ Literale hat und somit ein Paar von Implikationen beschreibt. Denn:
		\begin{align*}
			(x \vee y) &~\equiv (x \vee y) \vee (x \vee y) &\mathcomm{Idempotenz von $\vee$}\\
			&~\equiv (\neg\neg x \vee y) \vee (x \vee \neg\neg y) &\mathcomm{Doppelte Negation hebt sich auf}\\
			&~\equiv (\neg x \Rightarrow y) \vee (x \Leftarrow \neg y) &\mathcomm{Definition der Implikation}
		\end{align*}		
		Das Belegen einer Variable (mit \textsc{wahr}) innerhalb einer Implikation erzwingt eine Belegung der jeweils anderen Variable. Die Idee ist es nun, dass man für jede Variable die \enquote{Kette} der jeweils erzwungenen anderen Werte absucht. Wenn man eine Variable findet, die im Verlauf einer solchen Kette ihre Negation erzwingt, ist die gegebene Formel nicht erfüllbar. Hier ist es sinnvoll, gerichtete Graphen aus den Formeln zu konstruieren. Beispiel einer erfüllbaren Formel:
		\begin{gather*}
			\phi = (\neg x \vee y) \wedge (x \vee z) \wedge (\neg y \vee \neg z)
		\end{gather*}
		Die erste Klausel beschreibt die beiden Implikationen $(x \Rightarrow y)$ und $(\neg y \Rightarrow \neg x)$. Die zweite Klausel die beiden Implikationen $(\neg x \Rightarrow z)$ und $(\neg z \Rightarrow x)$. Und die dritte Klausel beschreibt die beiden Implikationen $(y \Rightarrow \neg z)$ und $(z \Rightarrow \neg y)$. Der zugehörige Graph ist:
		\begin{gather*}
			G = (\{x, \neg x, y, \neg y, z, \neg z\}, \{(x, y), (y, \neg z), (\neg z, x), (\neg x, z), (z, \neg y), (\neg y, \neg x)\})
		\end{gather*}
		Keine der drei Variablen erzwingt ihre Negation und somit ist die Formel erfüllbar.
		Beispiel einer nicht-erfüllbaren Formel:
		\begin{gather*}
			\rho = (x \vee y) \wedge (\neg x \vee y) \wedge (\neg x \vee \neg y) \wedge (x \vee \neg y)
		\end{gather*}
		Dabei ergibt sich als Graph (fast) vollständiger Graph mit den vier Knoten $\{x, \neg x, y, \neg y\}$. Die einzigen Kanten, die fehlen sind die zwischen $x$ und $\neg x$ bzw. $y$ und $\neg y$. Hier ergeben sich Kreise, die ein Literal als auch ihre Negation enthalten.
		
		Die Pfade in einem solchen Graphen kann man mithilfe von Tiefen- oder Breitensuche in Polynomzeit ermitteln. Darum ist auch der gesamte Algorithmus polynomiell. Man kann auch über \emph{starke Zusammenhangskomponenten} argumentieren: Wenn sowohl eine Variable als auch ihre Negation sich in der selben Zusammenhangskomponente befinden, dann ist die Formel nicht erfüllbar.
	\end{loesung}
	
	\begin{aufgabe}{2 + 2}
		\begin{enumerate}[\quad a)]
			\item Zeichnen Sie einen Graphen mit genau 5 Knoten, der sich \emph{nicht} mit 3 Farben färben lässt.
			\item Zeigen Sie: \textsc{Färbbarkeit} $\in \classNP$.
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item Hier könnte man einen $K_4$ zeichnen mit einer abstehenden Kante zeichnen. Da der Graph eine Clique der Größe 4 besitzt, kann er nicht mit 3 Farben gefärbt werden.
			\begin{figure}[h!]
				\centering
				\begin{tikzpicture}
					[nodedot/.style={draw,fill=blue,shape=circle,minimum size=.2cm,inner sep=0},
					nodelabel/.style={blue}]
					% nodes
					\node [nodedot,fill=magenta] (a) at (0, 0) {};
					% \node [nodelabel,anchor=east] at (a.west) {$a$};
					\node [nodedot] (b) at (0, 1) {};
					% \node [nodelabel,anchor=east] at (b.west) {$b$};
					\node [nodedot,fill=white] (c) at (1, 1) {};
					\node [nodelabel,anchor=south] at (c.north) {$\lightning$};
					\node [nodedot,fill=YellowGreen] (d) at (1, 0) {};
					% \node [nodelabel,anchor=west] at (d.east) {$d$};
					\node [nodedot] (e) at (2, 1) {};
					% \node [nodelabel,anchor=west] at (e.east) {$e$};
					% edges
					\draw (a) -- (b);
					\draw (a) -- (c);
					\draw (a) -- (d);
					\draw (b) -- (d);
					\draw (c) -- (b);
					\draw (c) -- (d);
					\draw (c) -- (e);
				\end{tikzpicture}
			\end{figure}
			\item Die Zugehörigkeit zu \classNP kann man mit einem \emph{Guess-and-Check}-Algorithmus zeigen:
				\begin{itemize}
					\item Rate eine Färbung $f \colon V \rightarrow \{1, \dots, k\}$
					\item Teste für alle $v_i, v_j \in V$ mit $v_i,v_j \in E$ ob $f(v_i) = f(v_j)$. Falls ja, lehne ab.
					\item Akzeptiere.
				\end{itemize}
				Der erste Schritt hat konstante oder lineare Laufzeit (je nach Definition des \enquote{Ratens}). Die Laufzeit des zweiten Schritts ist linear bzgl.\ der Kantenmenge (also auch der Eingabe). Der dritte Schritt hat konstante Laufzeit. Man kann die geratene Folge also in Polynomzeit überprüfen und damit gilt \textsc{Färbbarkeit} $\in \classNP$.
		\end{enumerate}
	\end{loesung}
\label{lastpage}
\end{document}