https://algo.iti.kit.edu/ 2026-04-21T08:35:41+00:00 https://algo.iti.kit.edu/ https://algo.iti.kit.edu/_media/favicon.ico text/html 2026-04-20T09:23:53+00:00 Anonymous (anonymous@undisclosed.example.com) https://algo.iti.kit.edu/teaching/sommer2026/proseminar_nphard_problems/index Proseminar: Schwere Probleme und die Kunst der Reduktion im Sommersemester 2026 Thema Die Berechnungskomplexität eines Problems ist eines der zentralen Konzepte in der Algorithmik. Neben dem Entwurf von effizienten Algorithmen sind auch theoretisch beweisbare untere Schranken für die Komplexität eines Problems von essentieller Bedeutung. Dies erlaubt unter anderem die Einteilung von Problemen in Komplexitätsklassen wie P, NP oder beispielsweise PSPACE. Untere Schranken, also die Schwere eines…