Zum Hauptinhalt springen

Willkommen bei der Fachgruppe Komplexität

Die Fachgruppe Komplexität ist ein Teil der Gesellschaft für Informatik. Diese Fachgruppe beschäftigt sich mit komplexitätstheoretischen Fragestellungen, insbesondere 

  • Komplexitätsklassen, Hierarchien,

  • untere und obere Komplexitätsschranken für spezielle Probleme,

  • Strukturfragen, Äquivalenzuntersuchungen

  • Einweg-, Falltürfunktionen, Kryptographie,

  • Interaktive Beweissysteme,

  • Komplexität logischer Entscheidungsprobleme,

  • logisch-deskriptive Komplexitätsklassen,

  • parametrisierte Komplexität,

  • Kolmogorov-Komplexität,

  • Nichtuniforme Berechnungsmodelle (spezielle Automaten, Schaltkreise, Branching-Programme, Formeln).

Manche der Themen sind eng gekoppelt an bzw. werden gemeinsam bearbeitet mit anderen Fachgruppen, insbesondere sind dies die FG Algorithmen (Thema: Obere Schranken), FG Automaten und formale Sprachen (Thema: spezielle Berechnungsmodelle, Abschlusseigenschaften von Klassen), FG Logik in der Informatik (Thema: Komplexität logischer Entscheidungsprobleme, Komplexität des logischen Programmierens, subrekursive Hierarchien).

Nächste Veranstaltungen