Jan Mehler Livres

In der Komplexitätstheorie wird untersucht, wie man den Ressourcenbedarf von Programmen einschätzen kann, obwohl dies im Allgemeinen nicht entscheidbar ist. Das Buch präsentiert ein Verfahren zur Generierung konkreter polynomieller Längenschranken für zertifizierbare Programme, das eine obere Schranke des Ressourcenbedarfs garantiert, jedoch bei Misserfolg keine Aussage über die Existenz einer Schranke trifft. Zudem werden die Grenzen dieser automatischen Generierung analysiert und gezeigt, wie das Verfahren zur Charakterisierung der Komplexitätsklassen FP, FLINSPACE und FPSPACE beiträgt.

In der Komplexitätstheorie ist lange bekannt, dass es im Allgemeinen nicht möglich ist Aussagen zum Ressourcenbedarf von Programmen zu entscheiden. So ist es z. B. unmöglich zu entscheiden, ob ein Programm eine polynomielle Laufzeit besitzt. Dennoch ist es möglich Verfahren zu entwickeln, die manchen Programmen einen maximalen Ressourcenbedarf zertifizieren können. Zertifizieren bedeutet hierbei, dass das Verfahren zwar im Erfolgsfall eine obere Schranke des Ressourcenbedarfs garantieren kann, aber bei Misserfolg nicht garantieren kann, dass eine solche Schranke nicht existiert. Dieses Buch beschreibt ein Verfahren, welches die Generierung von konkreten polynomiellen Längenschranken zu zertifizierbaren Programme ermöglicht. Eine solche Schranke gibt an, dass sich die Längen aller Ausgaben des Programms durch Polynome über den Längen der Eingaben beschränken lassen. Weiterhin werden die Grenzen einer solchen automatischen Generierung von polynomiellen Längenschranken untersucht und gezeigt wie durch das vorgestellte Verfahren die Komplexitätsklassen FP, FLINSPACE und FPSPACE charakterisiert werden können. Das Buch richtet sich an Komplexitätstheoretiker und den interessierten Leser.