Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Logik in der Informatik

Seminar Komplexität Boolescher Funktionen

Dozent: Prof. Dr. Christoph Berkholz

 

Inhalt

In diesem Seminar befassen wir uns mit der Komplexität von booleschen Funktion in eingeschränkten Berechnungsmodellen, wie Schaltkreisen oder Entscheidungsdiagrammen.

Im Gegensatz zur klassischen Komplexitätstheorie, in der boolesche Funktionen bzw. Entscheidungsprobleme bezüglich ihres Ressourcenverbrauchs auf Turingmaschinen charakterisiert werden und Härtebeweise häufig auf unbewiesenen Annahmen, wie P≠NP, beruhen, können untere Schranken an die Größe von bestimmten Schaltkreisen und Entscheidungsbäumen, die konkrete Funktionen berechnen, ohne komplexitätstheoretische Annahmen bewiesen werden.

Ziel des Seminars ist es, verschiedene Berechnungsmodelle für boolesche Funktionen zu kennenzulernen und sich Techniken zum Beweisen unterer Schranken anzueignen.

 

Zeit / Ort

Ort: Seminarraum RUD25, 3.408

Zeit: wird in Moodle bekannt gegeben, geplant ist:

  • Ein Vorbesprechungstermin Ende Oktober 2021.
  • Blockseminar an 2-3 Terminen im Januar/Februar 2022.

 

Organisation

Das Seminar ist als Blockseminar in Präsenz geplant. Um am Seminar teilzunehmen, schreiben Sie sich in AGNES ein.

Weitere Informationen und Termine werden in Moodle bereitgestellt. Der Einschreibeschlüssel zum Moodle-Kurs wird zum Vorlesungsbeginn an die in AGNES zugelassenen Studierenden verschickt.

 

Beachten Sie die aktuellen Hygieneregeln zur Teilnahme an Präsenzveranstaltungen.