complexity-classes.tex

\documentclass[
    13pt,
    oneside,
    a4paper,
    numbers=enddot,
    abstractoff,
    parskip=full
]{scrreprt}

\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{mathcomp}
\usepackage{eulervm}
\usepackage{mathpazo}


\renewcommand{\familydefault}{\sfdefault}


\begin{document}

\pagenumbering{gobble}




\chapter*{Complexity Classes}





DTM - Deterministic Turing Machine\\
NTM - Non-deterministic Turing Machine\\
PT - Probabilistic Turing Machine\\
PDTM - Deterministic Turing Machine \textit{running in polynomial time}\\
PNTM - Non-deterministic Turing Machine \textit{running in polynomial time}\\
PPT - Probabilistic Turing Machine \textit{running in polynomial time}\\
$n$ - Input length




\section*{Time Complexity Classes}
\label{sec:time_complexity_classes}

$\text{DTIME}(f) = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ DTM } T:
    T \text{ decides } A \land
    T \text{ runs in } \mathcal{O}(f(n))
~\}$
$\text{NTIME}(f) = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ NTM } T:
    T \text{ decides } A \land
    T \text{ runs in } \mathcal{O}(f(n))
~\}$


\begin{align*}
        P       &= \bigcup_{k \geq 1} \text{ DTIME}(n^k)
    &   NP      &= \bigcup_{k \geq 1} \text{ NTIME}(n^k)
    \\
        E       &= \bigcup_{k \geq 1} \text{ DTIME}(2^{kn})
    &   NE      &= \bigcup_{k \geq 1} \text{ NTIME}(2^{kn})
    \\
        EXP     &= \bigcup_{k \geq 1} \text{ DTIME}(2^{n^k})
    &   NEXP    &= \bigcup_{k \geq 1} \text{ NTIME}(2^{n^k})
\end{align*}






\section*{Space Complexity Classes}
\label{sec:space_complexity_classes}


$\text{DSPACE}(s) = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ DTM } T:
    T \text{ decides } A \land
    T \text{ uses } \mathcal{O}(s(n)) \text{ space}
~\}$
$\text{NSPACE}(s) = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ NTM } T:
    T \text{ decides } A \land
    T \text{ uses } \mathcal{O}(f(n)) \text{ space}
~\}$


\begin{align*}
    LOGSPACE     &= L =& \text{DSPACE}(\log n)
    \\
    NLOGSPACE    &= NL =& \text{NSPACE}(\log n)
    \\
    LINSPACE     &=& \text{DSPACE}(n)
\end{align*}
\begin{align*}
        PSPACE          &= \bigcup_{k \geq 1} \text{ DSPACE}(n^k)
    ~~~~=&  NPSPACE     &= \bigcup_{k \geq 1} \text{ NSPACE}(n^k)
    \\
        EXPSPACE        &= \bigcup_{k \geq 1} \text{ DSPACE}(2^{n^k})
    ~~~~=&  NEXPSPACE   &= \bigcup_{k \geq 1} \text{ NSPACE}(2^{n^k})
\end{align*}






\section*{Polynomial Hierarchy}
\label{sec:polynomial_hierarchy}


\begin{align*}
    \Delta^P_0 = \Sigma^P_0 = \Pi^P_0 &= P
    \\
        \Delta^P_{k+1} &= P^{\Sigma^P_k}
    &&  \Delta^P_1 = P ~~~& \Delta^P_2 &= P^{NP}
    \\
        \Sigma^P_{k+1} &= NP^{\Sigma^P_k}
    &&  \Sigma^P_1 = NP ~~~& \Sigma^P_2 &= NP^{NP}
    \\
        \Pi^P_{k+1} &= co\text{--}NP^{\Sigma^P_k}
    &&  \Pi^P_1 = co\text{--}NP ~~~& \Pi^P_2 &= co\text{--}NP^{NP}
\end{align*}

$ PH = \bigcup_{k \geq 0} \Delta^P_{k}
     = \bigcup_{k \geq 0} \Sigma^P_{k}
     = \bigcup_{k \geq 0} \Pi^P_{k} $




\section*{Probabilistic Complexity Classes}
\label{sec:probabilistic_complexity_classes}


\begin{align*}
    P & = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ PDTM } T:
    & \forall x \in A:      & \text{ P}(T(x)=1) = 1 ~\land \\
    & & \forall x \notin A: & \text{ P}(T(x)=1) = 0 ~\}
    \\
    NP & = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ PNTM } T:
    & \forall x \in A:      & \text{ P}(T(x)=1) > 0 ~\land \\
    & & \forall x \notin A: & \text{ P}(T(x)=1) = 0 ~\}
    \\
    PP & = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ PPT } T:
    & \forall x \in A:      & \text{ P}(T(x)=1) > 0.5 ~\land \\
    & & \forall x \notin A: & \text{ P}(T(x)=1) \leq 0.5 ~\}
    \\
    BPP & = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ PPT } T:
    & \forall x \in A:      & \text{ P}(T(x)=1) > 0.5 + \epsilon ~\land \\
    & & \forall x \notin A: & \text{ P}(T(x)=1) \leq 0.5 - \epsilon ~\}
    \\
    RP & = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ PPT } T:
    & \forall x \in A:      & \text{ P}(T(x)=1) > 0.5 ~\land \\
    & & \forall x \notin A: & \text{ P}(T(x)=1) = 0 ~\}
    \\
    ZPP & = \{
    A \in \Sigma^\ast ~|~
    \exists \text{ PPT } T:
    & \forall x \in A:      & \text{ P}(T(x)=1) > 0.5 ~\land \\
    & &                     & \text{ P}(T(x)=0) = 0 ~\land \\
    & &                     & \text{ P}(T(x)=\,?\,) \leq 0.5 ~\land \\
    & & \forall x \notin A: & \text{ P}(T(x)=1) = 0 ~\land \\
    & &                     & \text{ P}(T(x)=0) > 0.5 ~\land \\
    & &                     & \text{ P}(T(x)=\,?\,) \leq 0.5 ~\}
\end{align*}








\chapter*{Complexity Classes Relations}



\subsubsection*{Time Hierarchy Theorem}

$P \subset E \subset EXP$


\subsubsection*{Borodin-Trakhtenbrot Gap-Theorem}

$\forall$ total computable function $g$ with $g(n) \geq n$:\\
$\exists$ total computable function $f:$
    $ DTIME(f) = DTIME (g \circ f) $



\subsubsection*{Space Hierarchy Theorem}

$ L \subseteq NL \subset PSPACE \subset EXPSPACE $

$ L \subseteq NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE \subseteq EXP$


\subsubsection*{Savitch}

$ NSPACE(s(n)) \subseteq DSPACE(s(n)^2)$
\\
(compare to $ NTIME(f(n)) \subseteq DTIME(2^{\mathcal{O}(f(n))})$ )


\subsubsection*{Immerman-Szelepcsényi}

$s(n) \geq \log(n) \Longrightarrow NSPACE(s(n)) = co\text{--}NSPACE(s(n))$


\subsubsection*{Probabilistic World}

\begin{align*}
    P \subseteq~& ZPP \subseteq & RP \subseteq~& BPP & \subseteq PP \subseteq~& PSPACE
    \\
    P \subseteq~& ZPP \subseteq & RP \subseteq~& NP & \subseteq PP \subseteq~& PSPACE
    \\
    P \subseteq~& ZPP \subseteq & co\text{--}RP \subseteq~& co\text{--}NP & \subseteq PP \subseteq~& PSPACE
\end{align*}

$ RP \cap co\text{--}RP = ZPP $


\subsubsection*{Misc}

$ DIP = PV = NP \subseteq PH \subseteq PSPACE $

$ P = NP \Longleftrightarrow PH = P $

$ NP \neq co\text{--}NP \Longrightarrow P \neq NP $



\end{document}