Startseite

GI-Fachgruppe Komplexität

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

Fachgruppenleitung

• Arne Meier (Sprecher)
• Till Tantau (stellvertretender Sprecher)
• Jörg Rothe
• Thomas Schwentick
• Jacobo Torán

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

• Workshop über Algorithmen und Komplexität
• Protokoll des FG-Treffens vom 17.11.16, Hannover
• Protokoll des FG-Treffens vom 20.06.13, Hannover
• Protokoll des FG-Treffens vom 3.5.2007

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