Arbeitsgruppe Theoretische Informatik

ComplexityZoo++

Ansprechpartner: Malte Skambath 

Das Projekt "Complexity Zoo" [1,2] als eine bekannte umfangreiche Auflistung diverser Komplexitätsklassen, inklusive ihrer Beziehungen oder vermuteter Beziehungen zueinander zu nennen. Eine Schwäche des Projektes, welches unter anderem als ein Wiki organisiert gewartet wird, sind wenige Beispielprobleme für die Komplexitätsklassen und eine fehlende Unterscheidung verschiedener Arten von Komplexitätsklassen (z.B. für Entschiedungs-, Approximations- oder parameterisierte Probleme) und ggf. von Querverweisen, die in einem Wiki natürlich möglich ist.

Ziel dieses Projektes ist die Entwicklung neuen Systems zur Übersichtlichen Auflistung von Komplexitätsklassen, mit ihren Beziehungen und enthaltenen Problemen ermöglicht. Hierbei soll ermöglicht werden Probleme zu Komplexitätsklassen zuzuordnen, Beziehungen (Inklusionen) zwischen Klassen herzustellen und diese zu Kommentieren oder wenigstens mit Verweisen belegen zu können. Hierbei sollten auch verschiedene Arten von Problemen bzw. Klassen berücksichtigt werden können und für gegeben Probleme auch Beziehungen aufgebaut werden können (z. B. zwischen dem Entscheidungsproblem, parameterisierten Versionen, oder äquivalenten Problemen).

Quellen

  1. Scott Aaronson
    The Complexity Zoo​.
    http://cse.unl.edu/~cbourke/latex/ComplexityZoo.pdf
  2. Scott Aaronson, et al.,
    Complexity Zoo.
    https://complexityzoo.uwaterloo.ca/Complexity_Zoo