Computational Complexity (CC)5 ECTS
(englische Bezeichnung: Computational Complexity)

Lehrveranstaltungen:

• • Computational Complexity
    (Vorlesung, 2 SWS, Yiannis Giannakopoulos, Mo, 10:00 - 12:00, Übung 1 / 01.250-128)
  • Übung zu Computational Complexity
    (Übung, 1 SWS, Yiannis Giannakopoulos, Do, 12:00 - 14:00, Übung 5 / 01.254-128)

Inhalt:

This course covers:

• P, NP, and NP-completeness

• Complexity classes and reductions

• Boolean circuits

• The polynomial-time hierarchy

• Space complexity

• Randomized computation

• Counting complexity

• Introduction to the PCP theorem and hardness of approximation

• Average-case complexity

Lernziele und Kompetenzen:

Upon successful completion of the module, students are able to:

• have a rigorous understand of the concept of computation and its

formal limitations

• have knowledge of the fundamental complexity classes (including

P, NP and PSPACE)

• understand the notion of completeness and are able to design

and understand reductions between these classes

• are exposed to various formal computation models, including

Boolean circuits and randomness

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:

1. Artificial Intelligence (Master of Science)
   (Po-Vers. 2021s | TechFak | Artificial Intelligence (Master of Science) | Gesamtkonto | Nebenfach | Nebenfach Mathematik | Computational complexity)
2. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2017w | NatFak | Computational and Applied Mathematics (Master of Science) | Specialisation: Modeling and applied analysis (MApA) and optimization (Opti) | Computational complexity)
3. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2017w | NatFak | Computational and Applied Mathematics (Master of Science) | Specialisation: Numerical analysis and simulation (NASi) and optimization (Opti) | Computational complexity)
4. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2019w | NatFak | Computational and Applied Mathematics (Master of Science) | Gesamtkonto | Specialisation: Modeling and applied analysis (MApA) and optimization (Opti) | Computational complexity)
5. Computational and Applied Mathematics (Master of Science)
   (Po-Vers. 2019w | NatFak | Computational and Applied Mathematics (Master of Science) | Gesamtkonto | Specialisation: Numerical analysis and simulation (NASi) and optimization (Opti) | Computational complexity)
6. Data Science (Master of Science)
   (Po-Vers. 2021w | Gesamtkonto | Studienrichtung Databased optimization | Computational complexity)
7. Informatik (Bachelor of Science)
   (Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Gesamtkonto | Nebenfach | Nebenfach Mathematik | Computational complexity)
8. Informatik (Bachelor of Science)
   (Po-Vers. 2022w | TechFak | Informatik (Bachelor of Science) | Gesamtkonto | Nebenfach | Nebenfach Mathematik | Computational complexity)
9. Mathematik (Master of Science)
   (Po-Vers. 2015w | NatFak | Mathematik (Master of Science) | Gesamtkonto | Studienrichtung Modellierung, Simulation und Optimierung | Computational complexity)
10. Mathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Mathematik (Master of Science) | Gesamtkonto | Studienrichtung Modellierung, Simulation und Optimierung | Computational complexity)
11. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2015w | NatFak | Wirtschaftsmathematik (Master of Science) | Studienrichtung Optimierung und Prozessmanagement | Computational complexity)
12. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Studienrichtung Optimierung und Prozessmanagement | Computational complexity)
13. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Mathematische Wahlpflichtmodule | Studienrichtung Modellierung, Simulation und Optimierung | Computational complexity)
14. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Mathematische Wahlpflichtmodule | Specialisation: Modeling and applied analysis (MApA) and optimization (Opti) | Computational complexity)
15. Wirtschaftsmathematik (Master of Science)
    (Po-Vers. 2019w | NatFak | Wirtschaftsmathematik (Master of Science) | Gesamtkonto | Mathematische Wahlpflichtmodule | Specialisation: Numerical analysis and simulation (NASi) and optimization (Opti) | Computational complexity)

Studien-/Prüfungsleistungen:

Computational complexity (Prüfungsnummer: 50921)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet, 5 ECTS

Anteil an der Berechnung der Modulnote: 100.0 %

Erstablegung: SS 2022, 1. Wdh.: SS 2022

1. Prüfer:

Yiannis Giannakopoulos