0-main.tex

% Author: Philipp Moers <soziflip@gmail.com> 

\documentclass[12pt, oneside, a4paper, numbers=noenddot, abstracton, parskip=full]{scrreprt}

\input{sfliptex05.tex}
\input{conf.tex}

\begin{document}
\selectlanguage{ngerman}

\begin{titlepage}
    \begin{center}
        \Large{Ludwig-Maximilians-Universität München}\\[1cm]
        \large{\scshape{WS 2015/2016}}\\
        \large{\scshape{Martin Hofmann, Ulrich Schöpp}}\\[3cm]
        \Huge{\textbf{Komplexitätstheorie}}\\[5cm]
        \large{Vorlesungsmitschrieb von}\\[1cm]
        \large{Philipp Moers \\ 
        <p.moers@campus.lmu.de>\\
        <soziflip@gmail.com>}\\[2cm]
        \vfill
        \footnotesize{Stand: \today, \currenttime}
    \end{center}
\end{titlepage}

\begin{abstract}

    Die Komplexitätstheorie beschäftigt sich mit der Klassifikation von Algorithmen und Berechnungsproblemen nach ihrem Ressourcenverbrauch, z.\,B. Rechenzeit oder benötigtem Speicherplatz. Probleme mit gleichartigem Ressourcenverbrauch werden zu Komplexitätsklassen zusammengefasst. Die bekanntesten Komplexitätsklassen sind sicherlich P und NP, die die in polynomieller Zeit deterministisch bzw. nicht-deterministisch lösbaren Probleme umfassen.

    P und NP sind jedoch nur zwei Beispiele von Komplexitätsklassen. Andere Klassen ergeben sich etwa bei der Untersuchung der effizienten Parallelisierbarkeit von Problemen, der Lösbarkeit durch zufallsgesteuerte oder interaktive Algorithmen, der approximativen Lösung von Problemen, um nur einige Beispiele zu nennen.

    
    \begin{center}
    \textbf{Anmerkung}
    \end{center}

    Dies ist ein inoffizieller Vorlesungsmitschrieb. Als solcher erhebt er keinen Anspruch auf (NP-)Vollständigkeit oder Korrektheit. Nutzung, Anmerkungen und Korrekturen sind jedoch durchaus erwünscht! 

    Website der Vorlesung: \url{http://www.tcs.ifi.lmu.de/lehre/ws-2015-16/kompl}
    
\end{abstract}


\tableofcontents


\newpage

\input{1-einfuehrung.tex}
\input{2-turingmaschinen-berechenbarkeit-komplexitaetsklassen.tex}
\input{3-p-und-np.tex}
\input{4-platzkomplexitaet.tex}
% \input{5-alternierung-und-hierarchien.tex}
% \input{6-schaltkreise.tex}
% \input{7-interaktive-und-probabilistische-algorithmen.tex}


\end{document}