% Eine Mitschrift von Komplexitätstheorie
% https://wwwcip.cs.fau.de/~oj14ozun/kt.tex
% Veröffentlicht unter CC-BY-SA 4.0

\RequirePackage[l2tabu, orthodox]{nag}
\documentclass[a4paper,11pt,oneside,openany,fleqn,notitlepage]{memoir}

\usepackage[pdfusetitle,colorlinks]{hyperref}
\usepackage{microtype}
\usepackage{amsfonts,amssymb,amsmath,amsthm}
\usepackage[margin=2.61803398875cm]{geometry}
\usepackage{mathtools}
\usepackage{stmaryrd}
\usepackage{mathrsfs}
\usepackage{cleveref}
\usepackage{multicol}
\usepackage{attachfile}
\usepackage[colorspec=0.9]{draftwatermark}

\usepackage{polyglossia}
\setmainlanguage{german}

\usepackage{tikz}

\usepackage{xcolor}
\newcommand{\todo}{\textsf{\colorbox{red}{TODO}}}

\usepackage{imakeidx}
\makeindex

\theoremstyle{definition}
\newtheorem{definition}{Definition}[chapter]
\newtheorem{satz}{Satz}[chapter]
\newtheorem{lemma}{Lemma}[chapter]
\newtheorem{beh}{Behauptung}[chapter]

\DeclareMathOperator{\bin}{bin}
\DeclareMathOperator{\dk}{\texttt{\#}} %doppelkreuz

\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\qedsymbol}{$\blacksquare$}

\newcommand{\de}[1]{\emph{#1}\index{#1}}

% https://mirror.physik.tu-berlin.de/pub/CTAN/macros/latex/contrib/memoir/memman.pdf
% \chapterstyle{veelo}

\title{\Huge \textsc{Komplexitätstheorie}}
\author{
  Gelesen von Prof. Dr. Rolf Wanka\\
  an der FAU Erlangen\\[1cm]
  {\small Neu gesetzt im Sommersemester 2024}
}
\date{\today}

\begin{document}
\maketitle{}
{\small \tableofcontents{}}
\vfill
{
  \footnotesize \textbf{Achtung:} Es handelt sich bei diesem ``Skript'' um eine
  nicht-offizielle Mitschrift, welche während der Vorlesung
  aufgeschrieben wurde, primär basierend auf dem Tafelbild, und auf
  einem älterem Skript.  Fehler sind daher durchaus möglich, und
  können \href{https://wwwcip.cs.fau.de/~oj14ozun#contact}{mir} gerne
  gemeldet werden.  Dieses Dokument wie auch der \LaTeX{}-Quelltext
  wurden unter der
  \href{https://creativecommons.org/licenses/by/4.0/legalcode.de}{CC
    BY-SA 4.0 Lizenz} (Namensnennung und Weitergabe unter gleichen
  Bedingungen) veröffentlicht.  Der Quelltext sollte im
  \textattachfile[color=0 1 1]{kt.tex}{PDF Anhang} verfügbar sein.

  Die vorläufige URL unter der die neuste Version von diesem Dokument
  gefunden werden kann,
  sollte \url{https://wwwcip.cs.fau.de/~oj14ozun/kt.pdf} sein.

  Die offizielle Webseite findet sich auf der Webseite des Informatik
  Lehrstuhls \emph{Hardware-Software-Co-Design},
  \url{https://www.cs12.tf.fau.de/lehre/lehrveranstaltungen/vorlesungen/komplexitaetsthorie/}
}

\chapter{Einleitung}

\todo{}

\chapter{
  Turingmaschinen, Komplexitätsklassen und universelle
  Turingmaschinen
}

\todo{}

\begin{definition}
  Eine \de{Gödelisierung} einer 1-band Turingmanschine \(M\) besteht
  aus Wörtern \(w_{i,j,\ell,m}\) für jede Regel \(\delta(q_i, a_j) =
  (q_k, a_\ell, d_m)\) der Übergangsfunktion \(\delta\) von \(M\).
  Dabei repräsentieren wir  \(w_{i,j,\ell,m}\)
  durch \[\bin(i) \dk \bin(j) \dk \bin(k) \dk \bin(\ell) \dk \bin(m). \]

  Die verschiedenen \(w_{i,j,\ell,m}\) sind durch \(\dk\dk\) getrennt.
  Ende der \de{Gödelnummer}: \(\dk\dk\dk\).  Die TM mit Gödelnummer
  \(u\) hießt \(M_u\).  Die Gödelisürung von \(M\) hießt \(G(M)\).
\end{definition}

\begin{definition}
  Eine 1-Band-TM \(M_0\) heißt \de{universelle Turingmaschine}, falls gilt
  \[f_{M_0}(x) =
    \begin{cases}
      f_{M_0}(v) & \text{\(x = u \dk v\), \(u\) ist Gödelnummer}\\
      \text{undef.} & sonst
    \end{cases}\]
  \(M_0\) gestartet mit \(u \dk v\) hält genau dann, wenn \(M_u\)
  gestartet mit \(v\) hällt.
\end{definition}

\begin{satz}
  Es gibt eine universelle 1-Band-TM \(M_0\) mit:
  \[T_{M_0}(u \dk v) = O(T_{M_O}(v))\]
  und
  \[S_{M_0}(u \dk v) = O(S_{M_u}(v))\]
  \(u\) wird als konstant lang angesehen.
\end{satz}

\begin{satz}\label{satz:beschrankt-entscheidbar}
  Sei \(s: \mathbb{N} \to \mathbb{N}\) berechenbar.  Dann ist
  \[ H^{S(n)} \coloneq \{ u \dk v \mid \text{\(M_u\) gestartet mit \(v\)
      hält und benutzt höchstens \(s(|v|)\) Zellen} \}\] entscheidbar.
\end{satz}

\begin{lemma}
  Falls \(M\) eine \(s(n)\)-bandbeschränkte 1-Band-TM ist und
  gestartet mit \(x\) echt mehr als
  \({|Q|} \cdot s(|x|) \cdot |\Gamma|^{s(|x|)}\) Schritte macht, so
  hällt \(M\) gestartet mit \(x\) nicht.
\end{lemma}
\begin{proof}
  \(|w_1w_2| \leq s(|x|)\). D.h.

  \begin{itemize}
  \item Es gibt höchstens \(|\Gamma|^{s(|x|)}\) viele verscheide
    mögliche Bandinhalte.
  \item Der Kopf kann an \(s(|x|)\) vielen Stellen vorkommen.
  \item Je Kopfposition höchstens \(|Q|\) Zustände.
  \end{itemize}
  \[ |\Gamma|^{s(|x|)} \cdot s(|x|) \cdot |Q| \] ist die Maximalzahl
  an Konfigurationen.
\end{proof}

\begin{proof}[Beweis von \Cref{satz:beschrankt-entscheidbar}]
  \(H^{s(n)}\) wird folgendermaßen entschieden:
  \begin{itemize}
  \item Teste ob \(x = u \dk v\) ist, \(u\) Gödelnummer einer TM \(M_u\).
    Falls nein, verwerfe \(x\) und stop.
  \item Berechne \(n \coloneq |v|\).
  \item Berechne \(s(n)\).  (Geht, da \(s(n)\) berechenbar ist nach
    Voraussetzung)
  \item Berechne \(p = |Q| \cdot s(n) \cdot |\Gamma|^{s(n)}\)
  \item Benutze die universelle TM zur Simulation von \(M_u\)
    gestartet mit \(v\).  Benutze Zähler, der von \(p\) in jedem
    Schritt eine 1 abzieht.
  \item Verwerfe, falls \(M_u\) mit Eingabe \(v\) mehr als \(s(n)\)
    Speicherplatz benutzt oder mehr als \(p\) Schritte macht.  Sonst
    akzeptieren.
  \end{itemize}
\end{proof}

\chapter{Eine untere Schranke für 1-Band-TM}

\[ L \coloneq \left\{w\dk^{|w|}w \mid w \in \{0,1\}^\ast \right\}\]

Beispiel \(\verb!010###010! \in L\).

\begin{satz}\label{satz:untere-schranken}
  Für \(L\) gilt:
  \begin{enumerate}
  \item\label{item:untere-schranke-einband} \(L \in \mathrm{DTIME}_1(n^n)\)
  \item\label{item:untere-schranke-zweiband} \(L \in \mathrm{DTIME}_2(n)\)
  \item\label{item:untere-schranke-neinband} \(L \not\in
    \mathrm{DTIME}_1(t(n))\) für alle \(t(n) = o\left(n^n\right)\)
  \end{enumerate}
\end{satz}
\begin{proof}
  \Cref{item:untere-schranke-einband} und
  \Cref{item:untere-schranke-zweiband} gilt trivial.

  Zu \Cref{item:untere-schranke-neinband}: Sei \(M\) eine 1-Band-TM
  mit Zustandsmenge \(Q\).  Die Eingabe für \(M\) stehe zu Beginn in
  den Zellen \(0, 1, \dots, n-1\).  Am Ende stehe der Kopf von \(M\)
  auf Zelle \(0\).

  \begin{definition}
    Sei \(x\) eine Eingabe für \(M\), \(i\) die Nummer einer Zelle.
    Die \de{Crossing-Sequenz} \(\mathrm{CS}(x,i)\) auf Zelle \(i\) für
    Eingabe \(x\) ist die Folge der Zustände, die bei der Rechnung
    von \(M\) gestartet mit \(x\) jeweils direkt nach Kopfbewegungen
    von Zelle \(i-1\) nach \(i\) oder umgekehrt auftreten.
  \end{definition}

  \begin{lemma}\label{lem:kleben}
    Seien \(u, v, w, y \in \{0, 1, \dk\}^\ast\) so gewählt, daß
    \(\mathrm{CS}(uv, |u|) = \mathrm{CS}(wy,|w|)\) ist.  Dann gilt
    \[ uv \in L \iff uy \in L.\]
  \end{lemma}
  \begin{proof}
    Es reicht, \(uv \in L \implies wy \in L\) zu zeigen.
  \end{proof}
\end{proof}

Wir haben eine feste Form, TM aufzuschreiben.  Wort \(w \in
{0,1}^\ast\) kann beschreiben werden durch \(G(M)z\), so daß M
gestartet mit \(z\) das Wort \(w\) ausgibt.

\begin{definition}\label{def:kolmogorov}
  Für \(w \in {0,1}^\ast\) bezeichnet
  \(K(w) \coloneq \min \{ |G(M)z| \mid \text{\(M\) gestartet mit \(z\)
    berechnet \(w\)}\}\).
  die \de{Kolmogorov-Komplexität} von \(w\).
\end{definition}

\begin{lemma}\label{lem:over-kol-komplexity}
  Für jedes \(m \in \mathbb{N}\) gibt es ein \(w \in \{0,1\}^m\)
  mit \(K(w) \geq m\).
\end{lemma}
\begin{proof}
  Sonst wäre die Komplexität \(K(w) < m\) für alle \(w \in {0,1}^m\).
  Dann würde es für jedes \(w \in \{0,1\}^m\) ein \(u = G(M)z\),
  \(|u| < m\), so daß \(M\) gestartet mit \(z\) die Ausgabe \(w\)
  berechnet.  Da zu verschiedenen \(w\) auch verschiedene
  \(G(M)z \in {0,1}^\ast\) gehören, wäre
  \[ 2^m-1 = \sum_{i=0}^{m-1} 2^i = |{u \in {0,1}^\ast \mid |u| \lneq
      m} \geq |{0,1}^\ast| = 2^m \qquad \lightning \qedhere \]
\end{proof}

\begin{lemma}\label{def:min-kol-cs}
  Wir nehmen \(M = (Q, \Sigma, \Gamma, \delta, q_0, F)\) sei 1-Band-TM
  die \(L\) entscheidet.  Sei \(m \in \mathbb{N}\) fest.  Sei
  \(\hat{w} \in {0,1}^m\) so, daß \(K(\hat{w}) \geq m\) ist (Wegen
  \Cref{lem:over-kol-komplexity} gibt es \(\hat{w}\); \(\hat{w}\)
  hießt \de{Kolmogorov-zufällig}).  Dann hat bezüglich \(M\) für jedes
  \(i \in {m,\dots,2m-1}\) die Crossing-Sequenz \(CS(\hat{w} \dk^m
  \hat{w}, i)\) die Länge \(\Omega(m)\).
\end{lemma}
\begin{proof}
  Sei \(M = (Q, \Sigma, \Gamma, \delta, q_0, F)\) sei die 1-Band-TM,
  die \(L = \{w \dk^{|w|} w | w \in {0,1}^\ast\}\) entscheidet.  Sei
  \(m \in \mathbb{N}\) fest.  Sei \(w \in {0,1}^m\).  Ist auch nur
  eine Crossing-Sequenz \(CS(w \dk^m w, i)\) kurz, so ist \(K(w)\)
  klein.  Wir rekonstruieren aus Crossing-Sequenzen die Eingabe \(w
  \dk^m w\) für \(m\).  Für Kolmogorov-zufälliges \(\hat{w}\) erhalten
  wir somit lange Crossing-Sequenzen:

  Die TM \(\tilde{M}\) bekommt die Eingabe \(z \in {0,1}^\ast\), die
  als Binärkodierung einer Folge \(q_1, \dots, q_\ell\) von Zuständen
  von \(M\) interpretiert wird.  Gestartet mit \(q_1, \dots, q_\ell\)
  arbeitet \(\tilde{M}\) folgendermaßen:
  \begin{quote}
    \(\tilde{M}\) zählt nacheinander alle \(w \in {0,1}^\ast\) auf.
    Für jedes solche \(w\) startet sie \(M\) mit \(w \dk^{|w|} w\).
    \(\tilde{M}\) notiert dabei die Crossing-Sequenz
    \(\mathrm{CS}(w \dk^{|w|} w, i)\) für \(i \in {m, \dots, 2m-1}\).
    Falls eine davon mit \(q_\ell, \dots, q_\ell\) übereinstimmt, gibt
    \(\tilde{M} w\) aus (da sie auh \(w \dk^{|w|} w\) ``gefunden''
    hat) und stoppt.
  \end{quote}

  \begin{enumerate}
  \item \(|z| \leq \left\lfloor \log (|Q|) + 1 \right\rfloor \cdot
    \ell\)
  \item \(|G(\tilde{M}) = \mathcal{O}(1)\)
  \item Für jedes \(w \in {0,1}^m\)   gilt: \(\tilde{M}\) gestartet
    mit \(q_1, \dots, q_\ell = \mathrm{CS}(w \dk^m w, i)\) für
    irgendein \(i \in {m, \dots, 2m-1}\) gibt \(w\) aus.
  \end{enumerate}

  Sei
  \[\ell(w) = \min_{m \leq i \leq 2m-1} |\mathrm{CS}(w \dk^m w, i)|,\]
  dann folgt aus den Ausführungen
  \[K(w) = \emph{O}(|G(\tilde{M})| + \ell(w)) =
    \mathcal{O}(1+\ell(w))\] Für Kolmogorov-zufällig gilt:
  \(m \leq K(\hat{w}) = \mathcal{O}(1+\ell(\hat{w}))\), d.h.\
  \(\ell(\hat{w}) = \Omega(m)\).
\end{proof}

Daraus folgt, \(m\) ``\(\dk\)'' ergeben Laufzeit von mindestens
\(\Omega(n^2)\).

\chapter{Hierarchiesätze}
\label{def:hiersatz}

\begin{definition}
  \(s : \mathbb{N} \to \mathbb{N}\) heist \de{bandkonstuierbar}, falls
  es eine \(\mathcal{O}{s(n)}\)-beschränkte TM gibt, die bei Eingabe
  \(x\) die Binärdarstellung von \(s(|x|)\) berechnet.
\end{definition}

\begin{satz}[Bandhierarchiesatz]
  \(S : \mathbb{N} \to \mathbb{N}\) sei bandkonstruierbar, und für
  \(s : \mathbb{N} \to \mathbb{N}\) gelte \(s(n) = o(S(n))\).  Dann
  gilt:
  \[ \mathrm{DTAPE}(s(n)) \subsetneq \mathrm{DTAPE}(S(n)).\]
\end{satz}

\begin{proof}
  Sei                           %TODO: fold
  \begin{align*}
    L = \{ u \dk v \mid
    &\;\text{\(u\) Gödelnummer einer 1-Band TM \(M_u\).  \(M_u\) verwirft \(u \dk v\), \(S_{M_u}(u \dk v) < S(|u \dk v |)\),}\\
    &\;\text{die Rechnung benutzt keine Zellen links vom Kopf beim Start}\}
  \end{align*}

  \begin{lemma}\label{lem:geht-nicht-in-kleinen-platz}
    \(L \not\in \mathrm{DTAPE}(s(n))\)
  \end{lemma}
  \begin{lemma}\label{lem:geht-in-grossen-platz}
    \(L \in \mathtt{DTAPE}(S(n))\)
  \end{lemma}

  \begin{proof}[Beweis von \Cref{lem:geht-nicht-in-kleinen-platz}]
    Per Diagonalisierung.

    \paragraph{Annahme:} Es gibt eine
    \(\mathcal{O}(s(n))\)-bandbeschränkte TM \(M (= M_u)\), die \(L\)
    akzeptiert.  Wegen des ``Runtersimulierens'' können wir sagen:
    \(M\) ist 1-Band-TM.

    \paragraph{Weiterhin:} Kein ``links'' vom Start nötig.  Aus \(M\)
    ist \(\mathcal{O}(s(n))\)-bandbeschränkt und \(s(n) = o(S(n))\),
    folgt \[ \exists n_0 \forall x, |x| \geq n_0: S_M(x) < S(|x|). \]
    Wähle \(v\) mit \(|v| \geq n_0\).

    \paragraph{Was macht \(M_u\) mit \(u \dk v\)?}  \(S_{M_u}(u \dk v)
    < S(|u \dk v |)\)

    Daraus ergibt sich der Widerspruch:
    \[ u \dk v \in L \iff \text{\(M_u\) verwirft \(u \dk v\)} \iff u
      \dk v \in L \qedhere \]
  \end{proof}

  \begin{proof}[Beweis von \Cref{lem:geht-in-grossen-platz}]
    Folgende \(\mathcal{O}(S(n))\)-bandbeschränkte 2-Band TM
    akzeptiert \(L\):
    \begin{enumerate}
    \item Teste, ob \(x = u \dk v\), \(u\) Gödelnummer einer 1-Band
      TM.  Geht auf Platz \(\mathcal{O}(|x|) = \mathcal{O}(S(|x|))\).
      Falls nein: Verwerfe und halte.
    \item Berechnet \(S(|x|)\) (auf Platz \(\mathcal{O}(S(|x|))\) geht
      da bandkonstruierbar).
    \item Berechne
      \(|Q| \cdot S(|x|) \cdot \Gamma^{S(|x|)} + 1 \eqcolon T \) (Q
      Zustände von \(M_u\), \(\Gamma\) Bandalphabet von \(M_u\)) geht
      auch Platz \(\mathcal{O}(S(|x|))\).  \(T\) hat eine binäre Länge
      \(\mathcal{O}(S(|x|))\).
    \item Auf Band 2, nutze universelle TM.  Dabei steht die Eingabe
      für \(M_u\) auf Spur 1 (von Band 2).  Setze Marken in Abstand
      \(S(|x|)\) auf Spur 1.
    \item Simuliere \(T\) Schritte von \(M_u\) gestartet mit
      \(u \dk v\).

      Akzeptiere:
      \begin{itemize}
      \item Auf Spur 1 werden nur Zellen zwischen den Markern benutzt.
      \item \(M_u\) gestartet mit \(x\) hällt nach höchstens \(T\)
        schritten. (weil wir sonst in Endlosschleife sind).
      \item \(M_u\) verwirft \(x\).
      \end{itemize}

      Der Platzgebrauch ist \(\mathcal{O}(S(n))\).
    \end{enumerate}
  \end{proof}

  
\end{proof}

\appendix{}
\printindex{}

\end{document}

% LocalWords:  bandbeschränkte Bandinhalte Zustandsmenge Crossing
% LocalWords:  Turingmanschine Binärkodierung beschränkte
% LocalWords:  Binärdarstellung bandkonstruierbar

%%% Local Variables:
%%% mode: LaTeX
%%% TeX-master: t
%%% TeX-engine: xetex
%%% End: