GI-Fachgruppe Komplexität

Gesellschaft für Informatik e.V. GI-Fachgruppe Komplexität (KP)

Fachgruppenleitung

Mitgliedschaft

Sie werden Mitglied der Fachgruppe, indem Sie ein assoziiertes Mitglied der Fachgruppe werden. Die Mitgliedschaft ist kostenlos. Sie müssen kein GI-Mitglied sein, um Mitglied der Fachgruppe werden zu können.

Fachgruppenaktivitäten

Forschungsgebiete

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).