\begin{slide}{Komplexitätstheorie}

\dots für parallele Algorithmen

Klassen:
  \begin{itemize}
  \item NC $=$ polylogarithmische Zeit, 
    polynomielle Anzahl von Prozessoren

  \item P $=$ polynomielle Zeit  

  \item NC $\subseteq$ P
  \end{itemize}

Reduktionen:
\begin{itemize}
\item $\le_L$ logspace-Reduktion, Eigenschaften
\item P-vollständige Probleme
\end{itemize}



\end{slide}
