Extreme Uniformity

• Applicant: Privatdozent Dr. Andreas Krebs
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 245424250

Wann immer Problemstellungen gelöst werden, stellt sich nach dem Finden einer Lösung die Frage: Geht es noch besser? In der Informatik bedeutet das in der Regel, dass die Rechenzeit von Algorithmen minimiert werden soll. Für viele natürliche kombinatorische Probleme weisen die derzeit besten Algorithmen für manche Eingabeinstanzen einen untragbaren Bedarf an Rechenzeit auf. Bis heute ist es offen, ob das notwendig ist, oder ob es noch zu Verbesserungen kommen kann. Dieses ist das Untersuchungsgebiet der Komplexitätstheorie. In der Komplexitätstheorie wird nicht versucht, einen expliziten Algorithmus zu finden, sondern die Frage zu beantworten: Gibt es überhaupt einen besseren Algorithmus für ein Problem oder kann man umgekehrt beweisen, dass es keinen besseren Algorithmus gibt? Die komplexitätstheoretische Behandlung der Frage der Optimalität eines Algorithmus führte zu der Begriffsbildung der sogenannten Vollständigkeit: Der Rechenzeitbedarf von Problemen wird charakterisiert durch die Klasse von Problemen, die einen vergleichbaren Rechenzeitbedarf haben, so dass entweder alle diese Probleme in tragbarer Rechenzeit lösbar sind, oder alle gemeinsam nicht. Als Konsequenz, führte die Frage nach der Verbesserbarkeit einer Unzahl von kombinatorischen Alltagsproblemen zur Frage nach (Un)gleichheit der Klassen P und NP, die sich zu der vielleicht zentralsten Frage in der theoretischen Informatik entwickelt hat. Trotz der immensen Anstrengungen bei der Untersuchung des Verhältnisses von diversen Komplexitätsklassen sind die Erfolge in den meisten Fällen bis heute minimal. Das führte dazu, dass die behandelten Fragestellungen (in Form von Klassengleichheiten) modifiziert wurden durch Veränderung der zugrunde liegenden Berechnungsmodelle. Das in diesem Antrag verwendete Berechnungsmodell sind Schaltkreisfamilien. Die üblichen Ressourcen eines Algorithmus, wie Raum und Zeit, werden bei Schaltkreisen zu Parametern wie Größe und Tiefe. Im Bereich der Schaltkreiskomplexitätstheorie gibt es noch einen dritten Parameter: Uniformität. Die üblichen Berechnungsmodelle erlauben Eingaben von beliebiger Länge, Schaltkreise jedoch können nur Eingaben einer festen Länge verarbeiten. Deswegen werden in der Komplexitätstheorie nicht einzelne Schaltkreise, sondern Familien von Schaltkreisen betrachtet: ein Schaltkreis für jede Eingabelänge. Zudem haben wir einen (endlichen) Mechanismus, der uns für jede Eingabelänge den entsprechenden Schaltkreis erzeugen kann. Die Uniformität gibt also die Komplexität der Konstruierbarkeit des Schaltkreises zu einer Eingabelänge aus. Abhängig von den Ressourcen, die dieser Mechanismus verwenden kann, sprechen wir von verschiedenen Ebenen der Uniformität. Viele Fragestellungen der Schaltkreiskomplexitätstheorie, die seit über 30 Jahren offen sind, rücken in den Bereich des Lösbaren, wenn man die Uniformität der beteiligten Schaltkreise extrem einschränkt. Das Ziel dieses Arbeitsprogramms ist es, verschiedene Komplexitätsklassen unter extremer Einschränkung der Uniformität zu trennen, d.h. wir erlauben nur sehr begrenzte Mechanismen, die die Schaltkreisfamilien erzeugen. Daneben betrachten wir Komplexitätsklassen, die typischerweise nicht über Schaltkreise definiert sind, und erweitern den Begriff der extremen Uniformität auf diese Klassen.

• DFG Programme: Independent Junior Research Groups