\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}

% Regeln für TM -> MPCP
\newcommand{\ruleSa}{\textcolor{Aquamarine}{S1}}
\newcommand{\ruleKa}{\textcolor{Fuchsia}{K1}}
\newcommand{\ruleKb}{\textcolor{Apricot}{K2}}
\newcommand{\ruleKc}{\textcolor{ForestGreen}{K3}}
\newcommand{\ruleKd}{\textcolor{Magenta}{K4}}
\newcommand{\ruleUa}{\textcolor{SeaGreen}{U1}}
\newcommand{\ruleUb}{\textcolor{Sepia}{U2}}
\newcommand{\ruleUc}{\textcolor{orange}{U3}}
\newcommand{\ruleUd}{\textcolor{NavyBlue}{U4}}
\newcommand{\ruleLa}{\textcolor{Black}{L1}}
\newcommand{\ruleLb}{\textcolor{BlueViolet}{L2}}
\newcommand{\ruleLc}{\textcolor{Lavender}{L3}}
\newcommand{\ruleLd}{\textcolor{LimeGreen}{L4}}
\newcommand{\ruleLe}{\textcolor{RawSienna}{L5}}
\newcommand{\ruleLf}{\textcolor{CadetBlue}{L6}}
\newcommand{\ruleAa}{\textcolor{BrickRed}{A1}}

\newcommand{\ruleSaTop}{\textcolor{Aquamarine}{\#}}
\newcommand{\ruleKaTop}{\textcolor{Fuchsia}{0}}
\newcommand{\ruleKbTop}{\textcolor{Apricot}{1}}
\newcommand{\ruleKcTop}{\textcolor{ForestGreen}{\square}}
\newcommand{\ruleKdTop}{\textcolor{Magenta}{\#}}
\newcommand{\ruleUaTop}{\textcolor{SeaGreen}{z_0 0}}
\newcommand{\ruleUbTop}{\textcolor{Sepia}{z_0 1}}
\newcommand{\ruleUcTop}{\textcolor{orange}{z_0 \square}}
\newcommand{\ruleUdTop}{\textcolor{NavyBlue}{z_0 \#}}
\newcommand{\ruleLaTop}{\textcolor{Black}{0 z_f}}
\newcommand{\ruleLbTop}{\textcolor{BlueViolet}{1 z_f}}
\newcommand{\ruleLcTop}{\textcolor{Lavender}{\square z_f}}
\newcommand{\ruleLdTop}{\textcolor{LimeGreen}{z_f 0}}
\newcommand{\ruleLeTop}{\textcolor{RawSienna}{z_f 1}}
\newcommand{\ruleLfTop}{\textcolor{CadetBlue}{z_f \square}}
\newcommand{\ruleAaTop}{\textcolor{BrickRed}{z_f \# \#}}

\newcommand{\ruleSaBottom}{\textcolor{Aquamarine}{\# \square z_0 1 0 1 \square \#}}
\newcommand{\ruleKaBottom}{\textcolor{Fuchsia}{0}}
\newcommand{\ruleKbBottom}{\textcolor{Apricot}{1}}
\newcommand{\ruleKcBottom}{\textcolor{ForestGreen}{\square}}
\newcommand{\ruleKdBottom}{\textcolor{Magenta}{\#}}
\newcommand{\ruleUaBottom}{\textcolor{SeaGreen}{0 z_0}}
\newcommand{\ruleUbBottom}{\textcolor{Sepia}{1 z_0}}
\newcommand{\ruleUcBottom}{\textcolor{orange}{z_f \square}}
\newcommand{\ruleUdBottom}{\textcolor{NavyBlue}{z_f \#}}
\newcommand{\ruleLaBottom}{\textcolor{Black}{z_f}}
\newcommand{\ruleLbBottom}{\textcolor{BlueViolet}{z_f}}
\newcommand{\ruleLcBottom}{\textcolor{Lavender}{z_f}}
\newcommand{\ruleLdBottom}{\textcolor{LimeGreen}{z_f}}
\newcommand{\ruleLeBottom}{\textcolor{RawSienna}{z_f}}
\newcommand{\ruleLfBottom}{\textcolor{CadetBlue}{z_f}}
\newcommand{\ruleAaBottom}{\textcolor{BrickRed}{\#}}

% 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{8}
\newcommand\Abgabe{21.\,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}
		Analog zum Begriff der \classNP{}-Schwere nennen wir eine Sprache $L$ \classP{}-schwer (oder \classP{}-hart), wenn alle Sprachen aus \classP auf sie polynomial reduzierbar sind. Eine Sprache $L$ heißt \classP{}-vollständig, wenn sie in \classP liegt und \classP{}-schwer ist.
	\end{definition2}
	
	% \begin{aufgabe}{5}
		% Sei $M$ eine beliebige $k$-Band-Turingmaschine ($k > 1$), die in Zeit $\Oh{n}$ arbeitet. In welcher Zeit arbeitet eine Einband-Turingmaschine, die $M$ simuliert? Begründen Sie Ihre Antwort!
		
		% \Hinweis{Überlegen Sie sich, wie viel Mehraufwand ein \emph{einzelner} Schritt der Einband-Maschine gegenüber der Mehrband-Maschine hat. Betrachten Sie hierzu die Lösung von Übungsaufgabe 2.1b bzw.\ Satz 2.10 auf Seite 11 im Skript.}
	% \end{aufgabe}
	
	% \begin{loesung}
		% Im folgenden halten wir uns an die Lösung zu Aufgabe 2.1b. Das Aufteilen der Eingabe in Spuren ($a_1 \cdots a_n \vdash^{\ast} (a_1, \ast, \square, \ast, \dots \square, \ast) \cdots (a_n, \ast, \square, \ast, \dots \square, \ast)$) kostet Linearzeit. Weiter wird ein \emph{einzelner} Übergang der Mehrband-Maschine $\delta(z, a_1, \dots, a_k) = (z', b_1, \dots, b_k, L, \dots, L)$ wie folgt simuliert:
		% \begin{enumerate}[(i)]
			% \item[] (Beginne in Zustand $z_{Spur 1}$)
			% \item\label{enum:mtm:suche-kopf-2} Suche auf Spur $2$ das Kopfsymbol $\ast$.
			% \item\label{enum:mtm:ersetze-spur-1} Ersetze Symbol $a_1$ auf Spur $1$ zu $b_1$.
			% \item\label{enum:mtm:verschiebe-kopf-2} Verschiebe das Kopfsymbol $\ast$ auf Spur $2$ nach links.
			% \item[] (Wechsle in Zustand $z_{Spur 2}$)
			% \item\label{enum:mtm:schritte-rest} Wiederhole die drei Schritte für alle anderen Spur-Paare $(3,4), \dots, (2k-1,2k)$.
			% \item[] (Wechsle in Zustand $z'_{Spur 1}$)
		% \end{enumerate}
		
		% Die Suche nach dem Kopfsymbol $\ast$ (Schritt (\ref{enum:mtm:suche-kopf-2})) benötigt im Extremfall Linearzeit, da der Kopf potentiell über das gesamte Arbeitsband laufen muss. Das Ersetzen des zugehörigen Symbols und das Verschieben des Kopfsymbols (Schritte (\ref{enum:mtm:ersetze-spur-1}) und (\ref{enum:mtm:verschiebe-kopf-2})) benötigen konstante Zeit. Zusammen ergibt sich für das Bearbeiten einer Spur Linearzeit. Da es $k-1$ weitere Spuren gibt, auf denen diese Arbeitsschritte wiederholt werden (Schritt (\ref{enum:mtm:schritte-rest})) ergibt sich eine Gesamtlaufzeit von $\Oh{k \cdot n}$ um einen \emph{einzelnen} Schritt der Mehrband-Maschine zu simulieren und da die Mehrband-Maschine insgesamt $\Oh{n}$ Schritte benötigt, benötigt die simulierende Einband-Maschine $\Oh{n + n \cdot k \cdot n}$ Schritte. Da $k$ konstant ist, kann man die Laufzeit zu $\Oh{n^2}$ zusammen fassen.
	% \end{loesung}
	
	% \begin{aufgabe}{5}
		% Sei $A \defeq \left\{\text{\LinearAXXIX}^p\text{\LinearACXV}^q \colon p,q \in \setN ~\text{mit}~ p \neq q\right\}$. Zeigen Sie: Es gibt ein $c \in \setN$, sodass $A \in TIME(n+c)$
	% \end{aufgabe}
	
	% \begin{loesung}
		% Für $c \in \setN$ gilt $TIME(n+c) = \{A \subseteq \Sigma^{*} \colon \text{Es gibt eine Turingmaschine}~ M ~\text{mit}~ L(M) = A ~\text{und}~ time_M(w) \leq |w| + c\}$. Das heißt, wir müssen eine Mehrband-TM finden, die zu einem beliebigen Wort (der Länge $n$) in $n+c$ Schritten entscheiden kann, ob es von der Form $\text{\LinearAXXIX}^p\text{\LinearACXV}^q$ (mit $p \neq q$) ist. Eine solche TM (mit zwei Bändern) arbeitet beispielsweise folgendermaßen:
		% \begin{enumerate}[\quad 1.]
			% \item Laufe über die Eingabe auf dem ersten Arbeitsband und schreibe für jedes \text{\LinearAXXIX} eine Markierung auf das zweite Arbeitsband.
			% \item Falls ein \text{\LinearACXV} gefunden wird, dann lösche eine Markierung auf dem zweiten Arbeitsband. Laufe nun weiter auf dem ersten Band und lösche für jedes gefundene \text{\LinearACXV} eine Markierung auf dem zweiten Arbeitsband. Lehne ab, falls auf dem ersten Band erneut ein \text{\LinearACXV} gefunden wird, sonst akzeptiere. (In dem Fall gilt $p < q$.)
			% \item Falls auf dem ersten Band das Ende erreicht wird, prüfe, ob das zweite Arbeitsband leer ist. Wenn ja, lehne ab (in dem Fall gilt $p = q$), sonst akzeptiere (in dem Fall gilt $p > q$).
		% \end{enumerate}
		% Diese TM braucht ${|\text{\LinearAXXIX}^p\text{\LinearACXV}^q|} \eqdef n$ viele Schritte um ans Ende auf dem ersten Band zu gelangen und einen weiteren Schritt um zu prüfen, ob die Eingabe zu Ende ist und das zweite Arbeitsband leer ist. Das heißt, $A$ lässt sich in $n+1 \defeq n+c$ Schritten entscheiden und die Aussage gilt.
	% \end{loesung}
	
	\begin{aufgabe}{4}
		Zeigen Sie: $\left\{w \cdot \text{\LinearAXIX} \cdot w \colon w \in \left\{\text{\LinearACCCLXXIV},\text{\LinearACLXXV}\right\}^{\ast}\right\}$ ist in \classP.
	\end{aufgabe}
	
	\begin{loesung}
		Hierbei müssen wir eine TM konstruieren, die (deterministisch) in Polynomzeit entscheidet, ob ein Wort von der Form $w \cdot \text{\LinearAXIX} \cdot w$ ist, also ob das Wort aus zwei gleichen Wortteilen besteht, die durch das Trennsymbol \text{\LinearAXIX} getrennt sind. Folgende (grobe) Arbeitsweise beschreibt eine solche TM:
		\begin{itemize}
			\item Markiere den linken und den rechten Rand mit einem eigenen Symbol, bspw.\ \text{\LinearAXVI}.
			\item Lies das linkeste (nicht-Rand-)Symbol ein und speichere dieses (Zustand oder zweites Arbeitsband).
			\item Überschreibe das Feld mit einem $\square$ und gehe danach zum ersten Symbol (ungleich $\square$) nach dem Trennsymbol.
			\item Überprüfe, ob dieses Symbol gleich dem gespeicherten ist. Wenn nein: Lehne ab. Wenn ja: Überschreibe das Feld mit einem $\square$ und gehe wieder zum linkesten Symbol (ungleich $\square$ bzw.\ \text{\LinearAXVI}).
			\item Wiederhole den Vorgang, bis das linkteste Symbol das Trennzeichen \text{\LinearAXIX} ist. Akzeptiere, falls das Band rechts des Trennsymbols auch leer ist, sonst lehne ab.
		\end{itemize}
		
		Der erste Schritt (markieren der Ränder) hilft dabei, zu testen ob das Band rechts des Trennsymbols \text{\LinearAXIX} leer ist (d.\,h.\ bei der beschriebenen Arbeitsweise würde auch nur der rechte Rand reichen). Ohne diese Markierung würde die TM sonst nicht wissen, wie weit sie nach rechts laufen muss, um ein potentielles Zeichen aus $\left\{\text{\LinearACCCLXXIV},\text{\LinearACLXXV}\right\}$ zu finden. Statt den Randsymbolen kann man sich auch andere Möglichkeiten überlegen, wie man erkennt, wo das Wort ursprünglich zu Ende war (spezielle Blanksymbole, mitzählen der Wortlänge, beim Überprüfen des rechten Symbols testen, ob es das letzte Zeichen des Wortes ist, \dots).
		
		Um die Ränder des Wortes zu markieren müssen wir zweimal über die gesamte Eingabe laufen (einmal für den rechten Rand und einmal, um den Kopf wieder auf das erste Symbol in $w$ zu bewegen). Bei den restlichen Schritten (der \enquote{Hauptschleife}) laufen wir immer über die \enquote{halbe} Eingabe (Länge $|w|$) um zwei Zeichen zu vergleichen. Es werden insgesamt $|w|$ viele Vergleiche durchgeführt. Um zu testen, ob der rechte Teil der Eingabe leer ist, muss die TM potentiell nochmal über die halbe Eingabe laufen. Für ein Wort der Länge $n$ ergibt sich dann eine Laufzeit von $2 \cdot n + {|w|}^2 + |w| = {\left(\frac{1}{2} \cdot n\right)}^{2} + \frac{5}{2} \cdot n \in \mathcal{O}(n^2)$ gilt, haben wir eine in Polynomzeit arbeitende TM konstruiert.
	\end{loesung}
	
	\begin{aufgabe}{4}
		Zeigen Sie, dass jede Sprache $A \in \classP$ (außer $\emptyset$ und $\sigStar$) \classP{}-vollständig ist.
	\end{aufgabe}
	
	\begin{loesung}
		Nach Voraussetzung ist $A \in \classP$, also bleibt nur die \classP{}-Schwere zu zeigen. Sei $B \in \classP$ beliebig. Seien $a \in A$ und $b \notin A$ beliebig (da $\emptyset \subsetneq A \subsetneq \sigStar$ existieren beide Elemente). Wir betrachten folgende Reduktionsfunktion $f$ berechnet durch TM $M_f$:
		\begin{itemize}
			\item Simuliere $M_B$ mit der Eingabe $w$
			\item Falls $M_B$ akzeptiert, schreibe $a$ auf das Band
			\item Falls $M_B$ ablehnt, schreibe $b$ auf das Band
		\end{itemize}
		
		Damit gilt $w \in B \equiv f(w) \in A$. Die beiden letzten Schritte sind jeweils in konstanter Zeit möglich ($M_B$ berechnet eine charakteristische Funktion und die Ausgabe ist entweder $0$ oder $1$ -- also nur ein Zeichen, dass überschrieben werden muss). Der erste Schritt läuft in Polynomzeit, da nach Voraussetzung $B \in \classP$, also $M_B$ eine Polynomzeit-DTM ist. Da $B$ beliebig gewählt war heißt das, dass $A$ \classP{}-schwer und damit auch \classP{}-vollständig ist.
		
		\Bemerkung{Diese Aufgabe zeigt, dass die obige Definition zur \classP{}-Schwere überflüssig ist, da die Reduktionsfunktion selbst genug Ressourcen hat, um das gegebene Problem zu lösen. Typischerweise definiert man \classP{}-Schwere darum bzgl.\ einer \enquote{logarithmischen} statt einer polynomialen Reduktion.}
	\end{loesung}
	
	\begin{aufgabe}{4 + 3}
		\begin{enumerate}[a)]
			\item Zeigen Sie, dass \textsc{Sat} in \classNP ist.
		
			\Hinweis{Nutzen Sie aus, dass Formeln entweder innerhalb eines Klammerpaares stehen oder auf ein Negationszeichen folgen und Sie somit immer eine \enquote{innerste Formel} finden können, die Sie direkt auswerten können.}
			\item Spielen Sie Ihren Algorithmus mit der Beispielformel $\phi = ((v_1 \vee v_2) \wedge \neg v_2) $ durch.
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[a)]
			\item An dieser Stelle reicht ein einfacher \enquote{guess and check}-Algorithmus. Wir raten uns zu einer gegebenen Formel eine Belegung der Variablen und überprüfen dann in Polynomzeit, ob die Formel unter der geratenen Belegung \textsc{wahr} ist. Etwas Formaler: Sei $\phi$ eine aussagenlogische Formel mit den Variablen $v_1, ..., v_n$. Unsere NTM $M$ arbeitet folgendermaßen:
			\begin{itemize}
				\item Für $1 \leq i \leq n$: Rate eine Belegung für $v_i$.
				\item Ersetze in $\phi$ jedes Vorkommen von $v_i$ durch die zugehörige, geratene Belegung.
				\item Suche eine \enquote{innerste Formel} und ersetze den Ausdruck durch den passenden Wahrheitswert wie folgt:
					\begin{itemize}
						\item $\neg 0$ wird ersetzt durch $1$
						\item $\neg 1$ wird ersetzt durch $0$
						\item $(0 \vee 0)$ wird ersetzt durch $0$
						\item $(0 \vee 1)$ wird ersetzt durch $1$
						\item $(1 \vee 0)$ wird ersetzt durch $1$
						\item $(1 \vee 1)$ wird ersetzt durch $1$
						\item $(0 \wedge 0)$ wird ersetzt durch $0$
						\item $(0 \wedge 1)$ wird ersetzt durch $0$
						\item $(1 \wedge 0)$ wird ersetzt durch $0$
						\item $(1 \wedge 1)$ wird ersetzt durch $1$
					\end{itemize}
					In diesem Schritt müsste man formal noch ergänzen, dass die entstehenden $\square$-Symbole zwischen den Formel-Symbolen \enquote{gelöscht} werden, oder dass der Ersetzungsschritt diese ignoriert. (Also bspw.\ Statt $(1 \vee 0)$ durch $1$, $( \square^{\ast} 1 \square^{\ast} \vee \square^{\ast} 0 \square^{\ast} )$ durch $1 \square^{\ast}$ ersetzen.)
				\item Wiederhole den vorigen Schritt solange, bis keine inneren Formeln mehr vorhanden sind.
				\item Akzeptiere, wenn zum Schluss eine $1$ auf dem Band steht.
			\end{itemize}
			
			Das Raten der Belegungen und ersetzen der Werte erfolgt in konstanter Zeit (oder Polynomzeit, je nach \enquote{Interpretation} des Nichtdeterminismus). Sowohl das Ersetzen einer innersten Formel als auch das Finden einer solchen Formel ist in Polynomzeit möglich (hier muss die TM einmal über das Arbeitsband laufen). Da durch das Ersetzen der innersten Formeln die gesamte Formel immer kürzer wird, endet der Algorithmus auch irgendwann.
			\item Wenn man sich streng an die Syntax aus dem Skript hält, werden die Variablen binär kodiert (und brauchen somit mehr als ein Symbol). Wenn wir annehmen, dass entstehende leere Felder nicht gelöscht werden, ergibt sich folgender Ablauf:
				\begin{itemize}
					\arrayrulecolor{darkgray}
					\doublerulesepcolor{darkgray}
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$($ & $($ & $v$ & $0$ & $1$ & $\vee$ & $v$ & $1$ & $0$ & $)$ & $\wedge$ & $\neg$ & $v$ & $1$ & $0$ & $)$\\
						\hline
						\end{tabular}
					\item Geratene Belegung: $v_1 = 1$, $v_2 = 0$
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$($ & $($ & $1$ & $\square$ & $\square$ & $\vee$ & $0$ & $\square$ & $\square$ & $)$ & $\wedge$ & $\neg$ & $0$ & $\square$ & $\square$ & $)$\\
						\hline
						\end{tabular}
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$($ & $($ & $1$ & $\square$ & $\square$ & $\vee$ & $0$ & $\square$ & $\square$ & $)$ & $\wedge$ & $1$ & $\square$ & $\square$ & $\square$ & $)$\\
						\hline
						\end{tabular}
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$($ & $1$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\wedge$ & $1$ & $\square$ & $\square$ & $\square$ & $)$\\
						\hline
						\end{tabular}
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$1$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$ & $\square$\\
						\hline
						\end{tabular}
				\end{itemize}
				Wenn man Variablen als einzelne Symbole kodiert und leere Zellen \enquote{löscht}, ergibt sich folgender Ablauf:
				\begin{itemize}
					\arrayrulecolor{darkgray}
					\doublerulesepcolor{darkgray}
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$($ & $($ & $v_1$ & $\vee$ & $v_2$ & $)$ & $\wedge$ & $\neg$ & $v_2$ & $)$\\
						\hline
						\end{tabular}
					\item Geratene Belegung: $v_1 = 1$, $v_2 = 0$
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$($ & $($ & $1$ & $\vee$ & $0$ & $)$ & $\wedge$ & $\neg$ & $0$ & $)$\\
						\hline
						\end{tabular}
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$($ & 1 & $\wedge$ & $\neg$ & $0$ & $)$ & & & & \\
						\hline
						\end{tabular}
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$($ & 1 & $\wedge$ & $1$ & $)$ & & & & & \\
						\hline
						\end{tabular}
					\item \begin{tabular}{!{\color{darkgray}\vrule}!{\color{darkgray}\vrule} C{.8em} !{\color{darkgray}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{white}\vrule} C{.8em} !{\color{darkgray}\vrule}!{\color{darkgray}\vrule}}
						\hline
						$1$ & & & & & & & & & \\
						\hline
						\end{tabular}
				\end{itemize}
		\end{enumerate}
	\end{loesung}
\label{lastpage}
\end{document}