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
- 18.04. - 19.04.2024