\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{10}
\newcommand\Abgabe{--}
\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{ankuendigung}
		Dieses Übungsblatt wird nicht bewertet. Dennoch findet die Übung am 8. Februar statt um die Aufgaben zu besprechen.
	\end{ankuendigung}
	
	\begin{definition2}
		\small
		\begin{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}
			\item \underline{\textsc{Eulerpfad}-Problem}:
				\begin{itemize}
					\item \textbf{gegeben:} Ein ungerichteter Graph $G = (V, E)$
					\item \textbf{gefragt:} Gibt es einen Pfad, der jede \emph{Kante} im Graphen genau einmal besucht?
				\end{itemize}
			\item \underline{\textsc{Rucksack}-Problem}:
				\begin{itemize}
					\item \textbf{gegeben:} Eine Kapazität $K \in \setN$ und Gewichte $g_1, \dots, g_k \in \setN$
					\item \textbf{gefragt:} Gibt es eine Teilmenge $R \subseteq \{1, \dots, k\}$ mit $\sum_{i \in R} g_i = K$?
				\end{itemize}
			\item \underline{\textsc{$s$-$t$-Erreichbarkeit}}:
				\begin{itemize}
					\item \textbf{gegeben:} Ein gerichteter Graph und zwei Knoten $s$ und $t$
					\item \textbf{gefragt:} Gibt es einen Pfad von $s$ nach $t$?
				\end{itemize}
			\item \underline{\textsc{Faktorisierung}}:
				\begin{itemize}
					\item \textbf{gegeben:} Zwei natürliche Zahlen $n$ und $k$
					\item \textbf{gefragt:} Hat $n$ einen Primfaktor, der kleiner als $k$ ist?
				\end{itemize}
			\item \underline{\textsc{SuperMarioBros}}:
				\begin{itemize}
					\item \textbf{gegeben:} Ein beliebiges Level aus \emph{Super Mario Bros.}
					\item \textbf{gefragt:} Ist es möglich, das Ziel zu erreichen?
				\end{itemize}
			\item \underline{\textsc{Sokoban}}:
				\begin{itemize}
					\item \textbf{gegeben:} Ein beliebiges \emph{Sokoban}-Puzzle
					\item \textbf{gefragt:} Ist es möglich, alle Kisten auf Zielfelder zu schieben?
				\end{itemize}
			\item \underline{\textsc{InfiniteMinesweeper}}:
				\begin{itemize}
					\item \textbf{gegeben:} Ein beliebiges, teilweise gelöstes \emph{Minesweeper}-Feld
					\item \textbf{gefragt:} Ist es möglich die Lösung auf eine unendlich große Ebene auszuweiten?
				\end{itemize}
		\end{itemize}
	\end{definition2}
	\pagebreak
	
	\begin{aufgabe}{0}
		\begin{enumerate}[\quad (i)]
			\item Welche der folgenden Entscheidungsprobleme liegen in \classP?
			\item Welche liegen in \classNP? (Ohne, dass ein deterministischer Polynomzeitalgorithmus bekannt ist.)
			\item Für welche der Probleme ist noch nicht einmal ein nichtdeterministischer Polynomzeitalgorithmus bekannt?
		\end{enumerate}
		\begin{itemize}
			\item \textsc{Eulerpfad}-Problem
			\item \textsc{\textsc{Rucksack}-Problem}
			\item \textsc{$s$-$t$-Erreichbarkeit}
			\item \textsc{Faktorisierung}
			\item \textsc{$k$-Färbbarkeit}
			\item \textsc{SuperMarioBros}
			\item \textsc{Sokoban}
			\item \textsc{InfiniteMinesweeper}
		\end{itemize}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad (i)]
			\item \textsc{$s$-$t$-Erreichbarkeit}, \textsc{Eulerpfadproblem}
			\item \textsc{$k$-Färbbarkeit}, \textsc{Rucksack}-Problem, \textsc{Faktorisierung}, \textsc{SuperMarioBros}
			\item \textsc{Sokoban}, \textsc{InfiniteMinesweeper}
		\end{enumerate}
		Etwas mehr Informationen:
		\begin{itemize}
			\item \textsc{Eulerpfad}-Problem: Ein Graph hat einen Eulerpfad, gdw.\ er zusammenhängend ist und jeder Knoten (bis auf maximal zwei) eine gerade Valenz hat. Zusammenhang kann man mit Tiefensuche testen (Laufzeit linear in $\Oh{|V|+|E|}$) und Valenzen zählen ist möglich in $\Oh{|V|^2}$ ($|V|$ Knoten mit jeweils maximal $|V|$ Nachbarn). Das Problem liegt also (im Gegensatz zum \textsc{Hamiltonkreis}-Problem) in \classP.
			% \item \textsc{Schaltkreisauswertung} ist in \classP. Man kann einen Schaltkreis als Graph aufzeichnen. Diesen sortiert man topologisch und wertet die Knoten in Reihenfolge der topologischen Nummern aus. Das Problem ist sogar \classP-vollständig, aber die \classP-Schwere ist etwas aufwändiger zu zeigen. Man geht ähnlich vor wie bei der \classNP-Schwere von \textsc{Sat}: Man nimmt eine beliebige DTM und konstruiert aus der Folge der Rechenschritten einen Schaltkreis, der genau dann \textsc{True} ergibt, wenn die Maschine akzeptiert (vgl.\ [Richard E. Ladner: \enquote{The circuit value problem is log space complete for \classP}]). Das Problem ist analog zu \textsc{Sat} das \enquote{kanonische} \classP-vollständige Problem.
			\item \textsc{$s$-$t$-Erreichbarkeit} kann man sogar nichtdeterministisch in logarithmischem Platz (\classNL) lösen. Auch hier ist wieder ein Guess-and-Check-Algorithmus das Mittel der Wahl. Die einzigen Informationen, die gespeichert werden müssen sind der Knoten, der als nächstes betreten werden soll und die Anzahl der besuchten Knoten. Der Algorithmus endet, wenn Knoten $t$ erreicht wird (\enquote{akzeptieren}) oder der Pfad länger als $n$ Knoten ist (\enquote{ablehnen}). Wenn man binär (oder zumindest nicht unär) zählt, dann kann man eine Zahl $n$ in Platz $\Oh{log~n}$ aufschreiben.
			\item \textsc{Faktorisierung} ist in \classNP. Ein Guess-and-Check-Algorithmus (Faktor raten und überprüfen ob der Faktor prim ist) zeigt die Zugehörigkeit. Weiter ist das Problem auch in co-\classNP (Menge aller Probleme, deren \emph{Komplement} in \classNP liegt). Hier kann man auch einen Guess-and-Check-Algorithmus angeben (\enquote{rate} die Primfaktorzerlegung und überprüfe, ob jeder Faktor größer als $k$ ist) um das Problem zu lösen. Ob das Problem auch \classNP-schwer ist, ist noch unbekannt. Die landläufige Vermutung ist, dass das Problem \emph{nicht} \classNP-schwer ist. Wäre \textsc{Faktorisierung} \classNP-vollständig, dann würde \classNP = co-\classNP folgen. ($\classNP \stackrel{?}{=} \text{co-}\classNP$ ist ebenfalls eine \enquote{große} Frage der theoretischen Informatik.)
			\item Das \textsc{Rucksack}-Problem ist sogar \classNP-vollständig. Die Zugehörigkeit zu \classNP zeigt sich einfach über einen Guess-and-Check-Algorithmus. Die \classNP-Schwere kann man über eine Reduktion von \textsc{$3$-Sat} zeigen. Sei also $\Phi$ eine aussagenlogische Formel in konjunktiver Normalform. O.\,B.\,d.\,A.\ können wir annehmen, dass jede Klausel \emph{genau} drei Literale beinhaltet. $\Phi$ ist also von der Form $(z_{11} \wedge z_{12} \wedge z_{13}) \vee \cdots \vee (z_{m1} \wedge z_{m2} \wedge z_{m3})$ wobei alle $z_{ij} \in \{x_1 \dots, x_n, \neg x_1, \dots, \neg x_n\}$ sind. Wir konstruieren aus dieser Formel eine Instanz des \textsc{Rucksack}-Problems wie folgt:
			\begin{itemize}
				\item Sei $K$ eine Dezimalzahl, die mit $m$ Vieren anfängt und mit $n$ Einsen endet, also $K \defeq \underbrace{4\dots4}_{m}\underbrace{1\dots1}_{n}$ (bzw. $K = 4 \cdot 10^n \cdot \sum_{i=0}^{m-1} 10^i + \sum_{i=0}^{n-1} 10^i$).
				\item Seien die Gewichte $\{v_1, \dots, v_n, v'_1, \dots, v'_n, c_1, \dots, c_m, d_1, \dots, d_m\}$; wobei die einzelnen Zahlen wie folgt definiert sind:
				\item $v_i$ ist eine $m + n$-stellige Dezimalzahl, die an Stelle $k$ (von links) eine $1$ enthält, wenn das Literal $x_i$ in Klausel $C_k$ einmal vorkommt. (Analog steht an Stelle $k$ eine $2$ oder $3$, wenn die Variable zwei- bzw.\ dreimal in der Klausel vorkommt.) Weiter beinhaltet die Zahl eine $1$ an Position $m + i$ (d.\,h.\ im \emph{hinteren} Ziffernblock an Stelle $i$). Alle anderen Stellen sind $0$.
				\item $v'_i$ ist analog definiert, mit dem Unterschied, dass die Ziffern im linken Block dem Literal $\neg x_i$ entsprechen.
				\item $c_i$ ist eine $m + n$-stellige Dezimalzahl, die an Stelle $i$ eine $1$ enthält. Alle anderen Ziffern sind $0$.
				\item $d_i$ ist eine $m + n$-stellige Dezimalzahl, die analog an Stelle $i$ eine $2$ enthält. Alle anderen Ziffern sind $0$.
			\end{itemize}
			Wir müssen nun zeigen, dass $\Phi$ genau dann eine erfüllende Belegung hat, wenn es eine Teilmenge der oben definierten Zahlen gibt, die sich genau zu $K$ aufsummiert.
			
			\underline{$\Rightarrow$:} Sei eine erfüllende Belegung für $\Phi$ gegeben. Wir wählen von den oben definierten Zahlen alle $v_k$ für die gilt, dass $x_k$ mit \textsc{Wahr} belegt ist und alle $v'_k$ für die gilt, dass $x_k$ mit \textsc{Falsch} belegt ist. Da in einer validen Belegung keine Variable mit beiden Wahrheitswerten gleichzeitig belegt sein kann, gibt es auch kein $k$, so dass sowohl $v_k$ als auch $v'_k$ gewählt werden. Daraus folgt, dass die letzten $n$ Ziffern unserer Summe sich genau zu $\underbrace{1\dots1}_{n}$ aufsummieren. Die vorderen $m$ Ziffern sind jeweils höchstens $3$, da $\Phi$ in 3-KNF gegeben ist und damit ein einzelnes Literal nicht häufiger als dreimal in einer Klausel vorkommen kann. Da die Belegung $\Phi$ erfüllt, gilt ebenfalls, dass jede einzelne Klausel erfüllt ist und darum in jeder Klausel mindestens ein Literal \textsc{Wahr} ist. Das heißt, keine der vorderen $m$ Ziffern der Summe ist $0$. Man kann jetzt jede dieser einzelnen Ziffern zu genau $4$ aufsummieren, in dem man passend $c_k$ bzw.\ $d_k$ wählt. Zusammengefasst hat man aus der erfüllenden Belegung eine Teilmenge $R$ gewählt, die sich genau zu $K (= \underbrace{4\dots4}_{m}\underbrace{1\dots1}_{n})$ aufsummiert.
			
			\underline{$\Leftarrow$:} Sei eine Teilmenge $R$ gegeben, die aus den oben definierten Zahlen besteht und sich zu $\underbrace{4\dots4}_{m}\underbrace{1\dots1}_{n}$ aufsummiert. Um die \enquote{hinteren} $n$ Einsen zu erreichen muss für jedes $1 \leq k \leq n$ genau eine der Zahlen $v_k$ oder $v'_k$ gewählt sein. Keine andere Kombination liefert den $\underbrace{1\dots1}_{n}$-Teil am Ende. Weiter liefert das Aufsummieren der $c_k$ und $d_k$ höchstens $3$, also muss für jedes $1 \leq j \leq m$ zusätzlich ein passendes $v_k$ oder $v'_k$ gewählt werden. Die Wahl der $v_k$ bzw.\ $v'_k$ beschreibt somit eine erfüllende Belegung für $\Phi$.
			
			\underline{Beispiel:} Sei $\Phi = (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2 \vee x_4) \wedge (x_1 \vee x_4 \vee x_4)$. Damit ist $n = 4$ und $m = 3$ und wir wählen als Kapazität $K = 444\,1111$. Weiter wählen wir die anderen Zahlen wie folgt:
			\begin{align*}
				v_1 &= 101\,1000 & v'_1 &= 010\,1000\\
				v_2 &= 000\,0100 & v'_2 &= 110\,0100\\
				v_3 &= 100\,0010 & v'_3 &= 000\,0010\\
				v_4 &= 012\,0001 & v'_4 &= 000\,0001\\
				c_1 &= 100\,0000 &  d_1 &= 200\,0000\\
				c_2 &= 010\,0000 &  d_2 &= 020\,0000\\
				c_3 &= 001\,0000 &  d_3 &= 002\,0000
			\end{align*}
			Eine erfüllende Belegung für $\Phi$ ist $x_1 = x_4 = \textsc{Wahr}$ und $x_2 = x_3 = \textsc{Falsch}$. Wenn wir die $v_i$ bzw.\ $v'_i$ entsprechend der Belegung wählen, ergibt sich:
			\begin{align*}
				V\defeq~&v_1 + v_4 + v'_2 + v'_3 \\
				=~&101\,1000 \\
				+~&012\,0001 \\
				+~&110\,0100 \\
				+~&000\,0010 \\
				=~&223\,1111
			\end{align*}
			Wenn wir nun noch zusätzlich $d_1$, $d_2$ und $c_3$ zur Summe hinzufügen, ergibt sich:
			\begin{align*}
				V~+~& d_1 + d_2 + c_3 \\
				=~&223\,1111 \\
				+~&200\,0000 \\
				+~&020\,0000 \\
				+~&001\,0000 \\
				=~&444\,1111 = K
			\end{align*}
			Anderseits sieht man, wenn man eine nicht-erfüllende Belegung, wie bpsw.\ $x_1 = x_2 = x_3 = x_4 = \textsc{Falsch}$ wählt, dass sich als Summe der $v_i$ und $v'_i$ $120\,1111$ ergibt, welche man nicht mit Wahl von $c_i$ und $d_i$ zu $K$ aufsummieren kann, dann die $0$ an dritter Position höchstens zu $3$ aufsummiert wird.
			
			\item \textsc{$k$-Färbbarkeit} liegt in \classNP, wie auf dem letzen Übungsblatt gezeigt. Das Problem ist auch \classNP-schwer, sogar mit $k=3$. Dies kann man durch eine Reduktion von $3$-\textsc{Sat} zeigen (vgl.\ [Richard M. Karp: \enquote{Reducibility Among Combinatorial Problems}]). Grob erklärt: Aus einer gegebenen Formel (in 3KNF) erzeugt man einen Graphen, der genau dann 3-färbbar ist, wenn die Formel erfüllbar ist. Abbildung \ref{fig:3-color-graph} zeigt wie man den Graphen aufbaut.
			
			\begin{figure}[!ht]
			\centering
			\begin{tikzpicture}
				[nodedot/.style={draw,fill=blue,shape=circle,minimum size=.9cm,inner sep=0},
				nodelabel/.style={blue}]
				
				% nodes
				\node [nodedot,fill=green] (w) at (0, 0) {};
				\node [nodelabel,anchor=west] at (w.east) {\footnotesize($\mathrel{\widehat{=}} \textsc{Wahr}$)};
				
				\node [nodedot,fill=red] (f) at (2, -2) {};
				\node [nodelabel,anchor=west] at (f.east) {\footnotesize($\mathrel{\widehat{=}}\textsc{Falsch}$)};
				
				\node [nodedot,fill=yellow] (n) at (-2, -2) {};
				
				\node [nodedot,fill=none] (x1) at (-6, -4) {$x_1$};
				\node [nodedot,fill=none] (x1n) at (-4, -4) {$\neg x_1$};
				
				\node [nodelabel] at (-5, -5) {$\vdots$};
				
				\node [nodedot,fill=none] (xn) at (-6, -8) {$x_n$};
				\node [nodedot,fill=none] (xnn) at (-4, -8) {$\neg x_n$};
				
				\node [draw,minimum height=1.5cm,minimum width=1.1cm] (k1) at (0,-5) {$K_1$};
				\node [nodedot,fill=white,minimum size=.2cm,anchor=center] (k1in1) at ($(k1.south)+(.33, 0)$) {};
				\node [nodedot,fill=white,minimum size=.2cm,anchor=center] (k1in2) at (k1.south) {};
				\node [nodedot,fill=white,minimum size=.2cm,anchor=center] (k1in3) at ($(k1.south)+(-.33, 0)$) {};
				\node [nodedot,fill=white,minimum size=.2cm,anchor=center] (k1out) at (k1.north) {};
				\node [nodelabel] (k1in1dummy) at ($(k1in1)-(-.5,1)$) {};
				\node [nodelabel] (k1in2dummy) at ($(k1in2)-(0,1)$) {};
				\node [nodelabel] (k1in3dummy) at ($(k1in3)-(.5,1)$) {};
				
				\node [nodelabel] at (2, -5) {$\cdots$};
				
				\node [draw,minimum height=1.5cm,minimum width=1.1cm] (km) at (4,-5) {$K_m$};
				\node [nodedot,fill=white,minimum size=.2cm,anchor=center] (kmin1) at ($(km.south)+(.33, 0)$) {};
				\node [nodedot,fill=white,minimum size=.2cm,anchor=center] (kmin2) at (km.south) {};
				\node [nodedot,fill=white,minimum size=.2cm,anchor=center] (kmin3) at ($(km.south)+(-.33, 0)$) {};
				\node [nodedot,fill=white,minimum size=.2cm,anchor=center] (kmout) at (km.north) {};
				\node [nodelabel] (kmin1dummy) at ($(kmin1)-(-.5,1)$) {};
				\node [nodelabel] (kmin2dummy) at ($(kmin2)-(0,1)$) {};
				\node [nodelabel] (kmin3dummy) at ($(kmin3)-(.5,1)$) {};
				
				
				% edges
				\draw (w) -- (f);
				\draw (w) -- (n);
				\draw (f) -- (n);
				
				\draw (x1) -- (x1n);
				\draw (x1) -- (n);
				\draw (x1n) -- (n);
				
				\draw (xn) -- (xnn);
				\draw (xn) -- (n);
				\draw (xnn) -- (n);
				
				\draw (k1in1dummy) -- (k1in1);
				\draw (k1in2dummy) -- (k1in2);
				\draw (k1in3dummy) -- (k1in3);
				\draw (k1out) -- (n);
				\draw (k1out) -- (f);
				
				\draw (kmin1dummy) -- (kmin1);
				\draw (kmin2dummy) -- (kmin2);
				\draw (kmin3dummy) -- (kmin3);
				\draw (kmout) -- (n);
				\draw (kmout) -- (f);
				
				\draw [decorate,decoration={brace,amplitude=10pt},blue,xshift=-4pt,yshift=0pt] ($(kmin1dummy)+(0,-1)$) -- ($(k1in3dummy)+(0,-1)$) node [blue,midway,yshift=-.6cm] {\footnotesize Klauseln};
				\draw [decorate,decoration={brace,amplitude=10pt},blue,xshift=-4pt,yshift=0pt] ($(xn)+(-1,-.7)$) -- ($(x1)+(-1,.7)$) node [blue,midway,xshift=-1.25cm,yshift=.1em] {\footnotesize Variablen};
			\end{tikzpicture}
			\caption{\footnotesize Skizze eines zu einer aussagenlogischen Formel gehörenden Graphen}
			\label{fig:3-color-graph}
			\end{figure}
			
			Der Graph besteht aus zwei Knoten für jede Variable der Formel (wobei einer der Knoten der negierten Variable entspricht), einem Untergraphen (siehe Abbildung \ref{fig:3-color-clause-subgraph}) für jede Klausel der Formel und einem Dreieck, welches \enquote{vorgefärbt} ist. Jeden Variablen-Knoten verbindet man mit dem gelben Knoten des Dreiecks und zusätzlich mit dem zugehörigen, negierten Variablen-Knoten. Außerdem wird jeder Variablen-Knoten und jeder negierte Variablen-Knoten mit dem zugehörigen unteren Knoten (\enquote{Eingang}) des zugehörigen Klausel-Untergraphen verbunden (für eine Klausel $K_x = (x_i \wedge \neg x_j \wedge x_k)$ beinhaltet der Graph eine Kante vom Knoten $x_i$ zum ersten Eingang in $K_x$, vom Knoten $\neg x_j$ zum zweiten Eingang und vom Knoten $x_k$ zum dritten Eingang). Die oberen Knoten (\enquote{Ausgänge}) der Klausel-Untergraphen verbindet man jeweils mit dem gelben und dem roten Knoten des Dreiecks. Das Dreieck erzwingt zum einen, dass jede Variable und ihre jeweilige Negierung entweder grün oder rot gefärbt (also mit \textsc{Wahr} oder \textsc{Falsch} belegt) wird und zum anderen, dass jeder Klausel-Untergraph am Ausgang grün gefärbt werden muss.
			
			\begin{figure}[!ht]
			\centering
			\begin{tikzpicture}
				[nodedot/.style={draw,fill=blue,shape=circle,minimum size=.4cm,inner sep=0},
				nodelabel/.style={blue}]
				
				% nodes
				\node [nodedot,fill=none] (a) at (0, 0) {};
				\node [nodedot,fill=none] (b) at (1, 0) {};
				\node [nodedot,fill=none] (c) at (0, -1) {};
				\node [nodedot,fill=none] (d) at (2, 0) {};
				\node [nodedot,fill=none] (e) at (3, -1) {};
				\node [nodedot,fill=none] (f) at (0, -2) {};
				
				\node [nodelabel,anchor=east] at (a.west) {\footnotesize Eingang 1};
				\node [nodelabel,anchor=east] at (c.west) {\footnotesize Eingang 2};
				\node [nodelabel,anchor=east] at (f.west) {\footnotesize Eingang 3};
				\node [nodelabel,anchor=west] at (e.east) {\footnotesize Ausgang};
				
				% edges
				\draw (a) -- (b);
				\draw (a) -- (c);
				\draw (b) -- (c);
				\draw (b) -- (d);
				\draw (d) -- (e);
				\draw (d) -- (f);
				\draw (e) -- (f);
			\end{tikzpicture}
			\caption{\footnotesize Klausel-Untergraph}
			\label{fig:3-color-clause-subgraph}
			\end{figure}
			
			Die Klausel-Untergraphen sind so aufgebaut, dass der Ausgang nur dann grün gefärbt werden kann, wenn mindestens einer der mit den drei Eingängen verbundenen Variablen-Knoten grün gefärbt ist. Das bedeutet, dass der Klausel-Untergraph nur dann am Ausgangsknoten grün gefärbt werden kann, wenn die Klausel erfüllt werden kann. Und da der Graph nur dann 3-färbbar ist, wenn alle Ausgänge der Klausel-Untergraphen grün gefärbt werden können, gilt die Reduktionseigenschaft.
			
			Interessant ist, dass \textsc{$k$-Färbbarkeit} auch für \emph{festes} $k$ nicht zwingend in \classP liegt. Ein Bruteforce-Algorithmus (anders als bei bspw.\ \textsc{$k$-Clique}) hat eine Laufzeit in $\Oh{k^n}$. Je nach Eigenschaften des Graphen kann man das Problem aber dennoch \enquote{einfach} lösen. Es sind z.\,B. alle bipartiten Graphen 2-färbbar und alle planaren Graphen sind 4-färbbar (vgl.\ [Kenneth Appel und Wolfgang Haken: \enquote{Every Planar Map is Four Colorable}]).
			\item \textsc{SuperMarioBros} ist mit den üblichen Spielbedingungen (Zeitlimit, komprimierte Levelkodierung, \dots) \classNP-vollständig. Dies kann man bspw. mit einer Reduktion von $3$-\textsc{Sat} zeigen (vgl. [Greg Aloupis et al.: \enquote{Classic Nintendo Games are (Computationally) Hard}, 2012]). Die Reduktion funktioniert ähnlich wie bei der Reduktion von \textsc{$3$-Sat} zu \textsc{$3$-Färbbarkeit}: Man konstruiert Variablen- und Klausel-Gadgets als SMB-Teillevel. Diese setzt man dann so zusammen, dass man aus einer gegebenen Formel in 3-KNF ein SMB-Level erhält. (Für jede Variable ein Variablen-Gadget und für jede Klausel ein Klausel-Gadget, die man passend verbindet.) Im Fall von \textsc{SuperMarioBros} (und auch bei den meisten anderen solcher Reduktionen) muss noch ein Start- und ein Ziel-Gadget konstruiert werden. Prinzipiell müssen auch Gadgets konstruiert werden, die das Verbinden der einzelnen Gadgets ermöglichen -- im Fall von \textsc{$3$-Färbbarkeit} waren das die Kanten des Graphen.
			
			\begin{figure}[!ht]
				\centering
				\begin{subfigure}[t]{0.4\textwidth}
					\includegraphics[width=\textwidth,keepaspectratio]{smb-start}
				\caption{\footnotesize Start-Gadget}
				\label{fig:smb-start}
				\end{subfigure}
				\quad
				\begin{subfigure}[t]{0.4\textwidth}
					\includegraphics[width=\textwidth,keepaspectratio]{smb-ziel}
				\caption{\footnotesize Ziel-Gadget}
				\label{fig:smb-ziel}
				\end{subfigure}
				
				\vspace*{4em}
				
				\begin{subfigure}[t]{0.3\textwidth}
					\includegraphics[width=\textwidth,keepaspectratio]{smb-var}
				\caption{\footnotesize Variablen-Gadget}
				\label{fig:smb-var}
				\end{subfigure}
				\quad
				\begin{subfigure}[t]{0.4\textwidth}
					\includegraphics[width=\textwidth,keepaspectratio]{smb-clause}
				\caption{\footnotesize Klausel-Gadget}
				\label{fig:smb-clause}
				\end{subfigure}
			\caption{Gadgets}
			\label{fig:smb-start-ziel}
			\end{figure}
			
			Das Start-Gadget (Abbildung \ref{fig:smb-start}) ist ein Levelabschnitt, der Marios initiale Position und einen Fragezeichenblock mit einem Pilz beinhaltet. Das Ziel-Gadget (Abbildung \ref{fig:smb-ziel}) besteht aus einem Gang, bei dem ein Block zerstörbar ist, wenn Mario groß ist und aus dem eigentlich Ziel -- der Flagge. Das Variablen-Gadget (Abbildung \ref{fig:smb-var}) besteht aus zwei Eingängen (oben) und zwei Ausgängen (unten). Das Gadget ist so aufgebaut, dass wenn Mario von der oberen Kante runterspringt, er nicht mehr hoch springen kann. Die beiden Ausgänge entsprechen dem Belegen der Variable mit \textsc{Wahr} oder \textsc{Falsch} und sind mit den Klausel-Gadgets verbunden, welche das Literal enthalten. Das Klausel-Gadget (Abbildung \ref{fig:smb-clause}) besteht aus zwei Teilen und funktioniert prinzipiell so, dass Mario das Gadget durch einen der drei Eingänge oben (diese entsprechen den Literalen) betritt und auf den Koopa hüpft. Dann kann er den Panzer des Koopas nach unten schießen und damit die zerstörbaren Blöcke zerstören. Danach kann Mario das Gadget wieder nach oben Verlassen. Wichtig ist hier, dass Mario das Gadget wieder oben verlassen muss: Wenn er nach unten springt, dann kann er nicht nach oben zu einem der anderen Koopas springen, da der Abstand zu hoch ist. Weiter kann Mario nicht den selben Weg wie der Koopa-Panzer gehen, da der Gang nur ein Block hoch ist, Mario aber größer. Prinzipiell könnte Mario sich von einem Koopa treffen lassen (oder den Pilz am Anfang ignorieren) und dann durch den Gang gehen; wenn Mario es so bis zum Ziel-Gadget schafft, dann kann er allerdings dort die Flagge nicht erreichen. Das Ziel-Gadget erzwingt, dass Mario groß sein muss um das Level zu schaffen. Und da im Start-Gadget der einzige Pilz im ganzen Level ist, darf Mario sich von keinem der Koopas treffen lassen. Der zweite Abschnitt des Gadgets ist der untere (drei Blöcke hohe) Gang, der durch zerstörbare Blöcke zugesperrt ist. Dieser kann nur durchquert werden, wenn diese Blöcke zerstört wurden sind; also wenn Mario vorher das Gadget durch einen der oberen Eingänge betreten und einen Koopa-Panzer runtergeschossen hat.
			
			Da im Gegensatz zu \textsc{$3$-Färbbarkeit} die \enquote{Reihenfolge} wichtig ist (Mario durchläuft das Level Gadget für Gadget und ist nicht überall gleichzeitig), muss man die Gadgets passend verbinden. Aus einer aussagenlogischen Formel in 3-KNF (mit Variablen $x_1$ bis $x_n$ und Klauseln $K_1$ bis $K_m$) konstruiert man ein SMB-Level folgendermaßen: Das Level startet mit dem Start-Gadget. Dieses führt in ein Variablen-Gadget welches Variable $x_1$ entspricht. Der linke Ausgang wird mit der ersten Klausel-Gadget $K_i$ verbunden, welches die Variable enthält und der zweite Ausgang wird mit dem ersten Klausel-Gadget $K_j$ verbunden, welches $\neg x_1$ enthält. Klausel-Gadget $K_i$ wird dann mit dem nächsten Klausel-Gadget verbunden, welches $x_1$ enthält; $K_j$ mit dem nächsten Klausel-Gadget, welches $\neg x_1$ enthält. Die jeweils letzten Klausel-Gadgets die $x_1$ bzw.\ $\neg x_1$ enthalten werden danach mit Variablen-Gadget $x_2$ verbunden. Dieses dann wieder mit den entsprechenden Klausel-Gadgets usw. Die oberen Ein-/Ausgänge der jeweils letzten Klausel-Gadgets der letzten Variable $x_n$ werden dann mit dem unteren Gang des Klausel-Gadgets $K_m$ verbunden. Die Gänge werden dann untereinander verbunden (also $K_m$ nach $K_{m-1}$ usw.\ bis $K_2$ nach $K_1$). Der untere Gang in Klausel-Gadget $K_1$ wird dann zum Schluss noch mit dem Ziel-Gadget verbunden. Damit Mario in dem Level das Ziel erreichen kann, muss er also jedes Klausel-Gadget mindestens einmal betreten. Er betritt ein Klausel-Gadget genau dann, wenn er sich für die \enquote{richtige} Belegung der Variable entschieden hat. Mario kann also genau dann das Ziel erreichen, wenn die Formel erfüllbar ist.

			Ein neueres Paper ([Erik D. Demaine et al.: \enquote{Super Mario Bros. Is Harder/Easier than We Thought}, 2016]) analysiert \textsc{SuperMarioBros} im Speziellen nochmal und kommt zu Ergebnissen abhängig der Verallgemeinerung des Spiels: In \classP wenn der Bildschirm \enquote{beschränkt} ist und die Level unkomprimiert als Eingabe vorliegen (\textsc{SMB-standard}); (schwach) \classNP-vollständig wenn der Bildschirm \enquote{unbeschränkt} ist und die Level komprimiert als Einfabe vorliegen (\textsc{SMB-RLE}); \classPSPACE-vollständig wenn zusätzlich zu den vorigen Eigenschaften es Mario noch erlaubt ist, wieder nach links zu gehen (\textsc{SMB-general}). Für \textsc{SMB-standard} kann man einen Polynomzeitalgorithmus angeben; für \textsc{SMB-RLE} kann man eine Reduktion vom Rucksackproblem angeben und für \textsc{SMD-general} kann man eine Reduktion vom sogenannten \enquote{open-close door}-Framework angeben.
			\item \textsc{Sokoban} ist \classPSPACE-vollständig. Dies kann man durch eine Reduktion vom \emph{Erfüllbarkeitsproblem für quantifizierte boolesche Formeln} (\textsc{QBF}) zeigen. Eine quantifizierte boolesche Formel ist eine Formel der Form $\exists x_1 ~ \forall x_2 ~ \dots ~ \forall x_k ~ \phi(x_1, x_2, \dots, x_k)$. Wegen dem Allquantor kann man eine vorgegebene Lösung (Belegung der Exis\-tenz\-quan\-tor-Va\-ri\-a\-blen) \emph{nicht} auf naive Art in Polynomzeit testen. \textsc{QBF} ist analog zu \textsc{Sat} das \enquote{kanonische} \classPSPACE-vollständige Problem. (Genauer wurde eigentlich ein spezielles Framework (\enquote{Nondeterministic Constraint Logic} [vgl. Robert A. Hearn und Erik D. Demaine: \enquote{\classPSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation}, 2005]) entwickelt, das für die Reduktion zu solchen Be\-we\-gungs\-pla\-nungs-\-Pro\-ble\-men geeignet ist. Und die Komplexität dieses Frameworks wurde mit einer Reduktion von \textsc{QBF} gezeigt.)
			\item \textsc{Minesweeper} ist Turing-vollständig; vgl. [Richard Kaye: \enquote{Infinite versions of minesweeper are Turing complete}, 2007]). Die grundlegende Idee ist es, die Arbeitsweise einer beliebigen Turingmaschine durch eine Instanz des Minesweeper-Problems darzustellen. Die Startkonfiguration der TM entspricht dem vorgegebenen Muster des Minesweeper-Felds und die Konfigurationsübergänge werden durch Regeln simuliert, wie das vorgegebene Muster an bestimmten Stellen fortgesetzt werden kann. Die Reduktion ist so aufgebaut, dass die TM genau dann hält, wenn das Muster \emph{nicht} unendlich fortgesetzt werden kann (darum \underline{co-}\textsf{RE}-vollständig).
		\end{itemize}
		\emph{Randnotizen}:
		\begin{itemize}
			\item $\classNL \subseteq \classP \subseteq \classNP \subseteq \classPSPACE \subseteq \classNPSPACE \subseteq \classEXP$
			\item $\classNL \subsetneq \classPSPACE$ und $\classP \subsetneq \classEXP$, also müssen manche der Inklusionen oben \emph{echt} sein
			\item $\classPSPACE = \classNPSPACE$ (Satz von Savitch). Intuition: Platz kann man wiederverwenden. Unter der Annahme, dass man Zeit wiederverwenden kann gilt auch $\classP = \classNP$. \enquote{Zeit wiederverwenden} könnte man bspw.\ durch Zeitreisen; die zugehörige Komplexitätsklasse nennt sich $\classP\textsubscript{\textsf{CTC}}$ und für diese gilt $\classP\textsubscript{\textsf{CTC}} = PSPACE$ (vgl.\ [Scott Aaronson: \enquote{\classNP-complete Problems and Physical Reality}, 2005] oder [Todd A. Brun: \enquote{Computers with closed timelike curves can solve hard problems}, 2002]).
		\end{itemize}
	\end{loesung}
	
	\begin{aufgabe}{0}
		\begin{enumerate}[\quad a)]
			\item Geben Sie eine (Mehrband-)Turingmaschine $M$ an, die die Funktion $g \colon \setN \rightarrow \setN$ mit $g(n) = 11n $ berechnet. (\emph{Hinweis}: Sie müssen nicht unbedingt das Binärsystem nutzen.)
			\item Geben Sie eine Funktion $f \colon \setN \rightarrow \setN$ an, so dass $time_M(w) \leq f(|w|)$. (Begründen Sie Ihre Antwort.)
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		Eine Lösung ist es, wenn man als Ein- und Ausgabe Zahlen zur Basis 11 zulässt. Dann muss man nur eine Null ans Ende der Eingabe hängen. Bei dieser Lösung muss die TM ans Ende der Eingabe laufen, eine 0 schreiben und dann wieder an den Anfang der Eingabe laufen. Das heißt, sie braucht $|w|+1+|w \cdot 0| = 2|w| + 2$ Schritte. Wir setzen also $f(n) \defeq 2n + 2$.
			
		Eine andere Lösung ist es, wenn man das Unärsystem nutzt. Dann muss man zehn Kopien der Eingabe hinter die Eingabe schreiben. Zum kopieren nutzt man ein zweites Band. Man läuft über die Eingabe und kopiert jede gelesene $1$ auf das zweite Band. Wenn man am Ende der Eingabe angekommen ist, überschreibt man jede $1$ auf dem zweiten Band mit einer Markierung $1_2$ und schreibt eine $1$ auf das erste Band. Wenn man am Ende (bzw. Anfang) des zweiten Bands angekommen ist, dann läuft man wieder über das zweite Band und überschreibt jede Markierung mit $1_3$. Außerdem schreibt man eine $1$ für jede gefundene Markierung auf das erste Band. Diese Schritte wiederholt man solange, bis man die Eingabe insgesamt zehn (weitere) Male auf das Eingabeband geschrieben hat. Dann läuft man auf dem ersten Band wieder an den Anfang des Wortes (und löscht \enquote{unterwegs} das zweite Band). Die Maschine braucht $n$ Schritte um an das Ende des ersten Bandes zu kommen. Dann braucht sie jeweils weitere $n$ Schritte für jede Kopie der Eingabe (Also um jeweils die Markierungen $1_2$ bis $1_11$ zu verarbeiten). Am Ende braucht sie nochmal $11n$ Schritte um wieder an den Anfang des ersten Bandes zu kommen. Als Funktion ergibt sich also $f(n) \defeq n + 10n + 11n = 22n$.
		
		Eine weitere Lösung arbeitet im Dezimalsystem: Man kopiert die Zahl auf ein zweites Arbeitsband (um eine Stelle verschoben) und hängt an die Eingabe eine $0$. Dann steht auf dem ersten Band $10n$ und auf dem zweiten Band $n$. Dann addiert man beide Bänder wie bei der schriftlichen Addition. Hier ergibt sich ebenfalls als Funktion $f(n) \defeq 2n + 2$, da die TM ans Ende der Eingabe laufen muss, ein Zeichen hinzufügen muss, und dann wieder an den Anfang (der nun eins längeren) Eingabe laufen muss.
		
		Im Binärsystem kann man ähnlich verfahren, denn $11n = 8n + 2n + n$. Also kann man drei Arbeitsbänder nutzen. Eines der Bänder enthält die Eingabe, ein zweites die Eingabe um eins nach links verschoben (mit einer zusätzlichen Null am Ende) und ein drittes die Eingabe um drei nach links verschoben (mit drei zusätzlichen Nullen am Ende). Dann kann man auch hier wie beim schriftlichen Addieren die Bänder zusammenrechnen. Als Laufzeit ergibt sich analog $f(n) \defeq 2n + 6$.
	\end{loesung}
	
	\begin{aufgabe}{0}
		Gegeben ist eine Turingmaschine $M = (S, E, A, \delta, z_0, \square, F)$ mit Zustandsmenge $S = \{z_0, z_1, z_2, z_e\}$, Eingabealphabet $E = \{0,1\}$, Bandalphabet $A = \{0, 1, \square\}$, Blanksymbol $\square$, Startzustand $z_0$, Endzustandsmenge $F = \{z_e\}$ und Zustandsüberführungsfunktion $\delta$ mit:
		\begin{center}
		\begin{tabular}[c]{r | c c c}
			$\delta(z,w)$ & 0 & 1 & $\square$ \\ \hline
			$z_0$ & $(z_0, \square, R)$ & $(z_1, 1, R)$ & $(z_2, 1, N)$ \\
			$z_1$ & $(z_1, 0, R)$ & $(z_1, 1, R)$ & $(z_2, 1, N)$ \\
			$z_2$ & $(z_2, 0, L)$ & $(z_2, 1, L)$ & $(z_e, 1, N)$
		\end{tabular}
		\end{center}
		\begin{enumerate}[\quad a)]
			\item Geben Sie die Folge der Konfigurationen an, die $M$ bei Eingabe $010$ durchläuft.
			\item Welche Funktion $s: \{0,1\}^{*} \rightarrow \{0,1\}^{*}$ und welche Funktion $f: \setN \rightarrow \setN$ berechnet $M$?
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		Die Maschine löscht alle führenden Nullen und schreibt dann eine Eins ans Ende und an den Anfang des übrigen Wortes.
		\begin{enumerate}[\quad a)]
			\item $z_0 010 \vdash \square z_0 10 \vdash \square 1 z_1 0 \vdash \square 10 z_1 \square \vdash \square 10 z_2 1 \vdash \square 1 z_2 01 \vdash \square z_2 101 \vdash z_2 \square 101 \vdash z_e 1101$
			\item \begin{itemize}
					\item $s: \{0,1\}^{*} \rightarrow \{0,1\}^{*}$, $w \mapsto 1 \cdot w' \cdot 1$ (mit $w = 0^{*} \cdot w'$). 
					
					Bzw. etwas \enquote{formaler}: $w \mapsto \begin{cases}1 \cdot w \cdot 1 &(w \neq 0 \cdot w')\\s(w') &(w = 0 \cdot w')\end{cases}$
					\item $f: \setN \rightarrow \setN$, $n \mapsto (2n+1) + 2^{\ell(2n+1)}$, wobei $\ell(n) = $ \enquote{Die Länge der Zahl im Binärsystem}. (Es gilt $\ell(n) = \floor{log(n)} + 1$.)
				  \end{itemize}
		\end{enumerate}
	\end{loesung}
	
	\begin{aufgabe}{0}
		Schreiben Sie ein \textsc{Loop}- oder \textsc{While}-Programm, das $x^y$ berechnet. Vermeiden Sie die explizite Multiplikation.
	\end{aufgabe}
	
	\begin{loesung}
		\begin{center}
		\begin{minipage}[t]{0.8\textwidth}
		\begin{tt}
			$x_0 \defeq 1$ \\
			LOOP $y$ DO \\
			\hspace*{1em} $s \defeq 0$ \\
			\hspace*{1em} LOOP $x$ DO \\
			\hspace*{2em} $s \defeq s + x_0$ \\
			\hspace*{1em} END \\
			\hspace*{1em} $x_0 \defeq s$ \\
			\hspace*{1em} END \\
			END
		\end{tt}
		\end{minipage}
		\end{center}
	\end{loesung}
	
	\begin{aufgabe}{0}
		Sind die folgenden Aussagen wahr oder falsch? (Begründen Sie Ihre Antworten.)
		\begin{enumerate}[\quad i)]
			\item Jede nicht-entscheidbare Menge enthält eine entscheidbare Teilmenge.
			\item Jede Teilmenge einer entscheidbaren Menge ist entscheidbar.
			\item Aus $A$ entscheidbar und $A \cap B$ entscheidbar folgt $B$ entscheidbar.
			\item Die Menge $\{(w,x) \in E^{*} \times \setN \colon M_w(x) = x^2\}$ ist entscheidbar.
			\item Für $h_M(w) \colon E^{*} \rightarrow \{0,1\}$ mit ($h_M(w) = 1 \equiv M(w)~\text{hält}$) gilt $A = \{h_M(w)\}$ ist entscheidbar.
		\end{enumerate}
	\end{aufgabe}
		
	\begin{loesung}
		Sind die folgenden Aussagen wahr oder falsch? (Begründen Sie Ihre Antworten.)
		\begin{enumerate}[\quad i)]
			\item Ja, denn $\emptyset \subseteq X$ für alle $X$.
			\item Nein. $E^{*}$ ist entscheidbar, aber $H \subseteq E^{*}$ ist nicht entscheidbar.
			\item Nein. Sei $A = \emptyset$, dann ist $A \cap B = \emptyset$ ebenfalls entscheidbar, auch für nicht-entscheidbares $B$.
			\item Nein, wegen des Satzes von Rice.
			\item Ja, denn jede endliche Menge ist entscheidbar und $A \subsetneq \{0,1\}$ ist endlich.
		\end{enumerate}
	\end{loesung}	
		
	\begin{aufgabe}{0}
		Sei $h$ eine totale und surjektive Funktion, die als Bildbereich die \emph{komplette} Menge aller einstelligen berechenbaren Zahlenfunktionen hat, also:
		\begin{gather*}
			h \colon \setN \rightarrow \{f \colon \setN \rightarrow \setN \colon f~\text{ist eine totale berechenbare Funktion}\}
		\end{gather*}
		Das heißt, für jedes $n \in \setN$ ist $h(n)$ eine Funktion von $\setN$ nach $\setN$ und $h(n)(x)$ ist der Wert der Funktion $h(n)$ an Stelle $x$.
		
		Zeigen Sie, dass die folgende Funktion nicht berechenbar ist:
		\begin{gather*}
			g \colon \setN^2 \rightarrow \setN,~g(n,x) = h(n)(x)
		\end{gather*}

		\Hinweis{Konstruieren Sie aus $g$ eine einstellige totale Funktion, welche im Bildbereich von $h$ liegen würde und zeigen Sie mithilfe von Diagonalisierung (ähnlich zu Kapitel 5 in den Folien) einen Widerspruch auf.}
	\end{aufgabe}
	
	\begin{loesung}
		Angenommen $g$ sei berechenbar. Dann wäre $g' \colon \setN \rightarrow \setN$ mit $g'(x) = g(x,x) + 1 (= h(x)(x)+1)$ auch berechenbar. Weiter gilt: $g'$ ist total (da sowohl $h$ als auch $h(x)$ total sind). Daraus folgt, dass $g'$ im Bildbereich von $h$ liegt -- es gibt also ein $z \in \setN$ mit $h(z) = g'$. Insbesondere gilt dann $g'(z) = h(z)(z) = g(z,z)$. Nach Definition von $g'$ gilt allerdings $g'(z) = g(z,z) + 1 \lightning$.
	\end{loesung}
	
	\begin{aufgabe}{0}
		Zeigen Sie die folgenden Aussagen:
		\begin{enumerate}[\quad a)]
			\item $\{(n,k) \in \setN^2 \colon n~\text{hat einen Primfaktor kleiner}~k\}$ ist entscheidbar.
			\item $\{(x,y,z) \in \setN^3 \colon (\exists n \in \setN) ~ x^n + y^n = z^n\}$ ist semi-entscheidbar.
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item $\{(n,k) \in \setN^2 \colon n ~\text{hat einen Primfaktor kleiner}~k\}$ kann man mit folgendem Algorithmus entscheiden:
				\begin{algorithmic}[1]
					\State $i \leftarrow 2$
					\While{$i < k$}
						\If{$n \equiv 0~(mod~i)$} \Comment{$i$ teilt $n$}
							\State \Return{\True}
						\EndIf
						\State $i \gets i+1$
					\EndWhile
					\State \Return{\False}
				\end{algorithmic}
				Der Algorithmus testet alle potentiellen Teiler und gibt \True zurück, wenn ein Teiler gefunden wird. Wenn kein Teiler (in $\{2, \dots, k-1\}$) gefunden wird, dann besitzt die Zahl keinen Primfaktor kleiner $k$ und der Algorithmus liefert \False zurück. Prinzipiell könnte man noch testen, ob das gefundene $i$, welches $n$ teilt eine Primzahl ist oder nicht. Falls $i$ eine Primzahl ist, dann ist $i$ ein Primfaktor. Falls $i$ keine Primzahl ist, dann hat $i$ selbst allerdings eine Primfaktorzerlegung, wobei jeder Primfaktor kleiner als $i$ selbst ist und jeder der Primfaktoren von $i$ auch $n$ teilt (folgt alles mehr oder weniger aus dem \emph{Fundamentalsatz der Arithmetik}).
			\item $\{(x,y,z) \in \setN^3 \colon \exists n \in \setN ~ x^n + y^n = z^n\}$ lässt sich mit folgendem Algorithmus \enquote{semi-entscheiden}:
				\begin{algorithmic}[1]
					\State $i \leftarrow 1$
					\While{$x^i + y^i \neq z^i$}
						\State $i \gets i+1$
					\EndWhile
					\State \Return{\True}
				\end{algorithmic}
				Der Algorithmus testet für alle natürlichen Zahlen, ob die Gleichung erfüllt ist. Wenn er eine Zahl findet, für die die Gleichung gilt, liefert er \True zurück, sonst rechnet er weiter. Da Addition und Potenzierung \textsc{While}-berechenbar sind, ist auch die Schleifenbedingung \textsc{While}-berechenbar und damit ist der Algorithmus ein Semi-Entscheidungsverfahren. Prinzipiell ist die Menge sogar entscheidbar, da man nur $n=1$ und $n=2$ testen muss. Für alle $n>2$ ist die Gleichung immer falsch (\emph{Großer Fermat'scher Satz}).
		\end{enumerate}
	\end{loesung}
\label{lastpage}
\end{document}