Computational Complexity (CC)5 ECTS
(englische Bezeichnung: Computational Complexity)
(Prüfungsordnungsmodul: Computational complexity)

Lectures:

• • Computational Complexity
    (Vorlesung, 2 SWS, Yiannis Giannakopoulos, Mon, 10:00 - 12:00, Übung 1 / 01.250-128)
  • Übung zu Computational Complexity
    (Übung, 1 SWS, Yiannis Giannakopoulos, Thu, 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:

1. Artificial Intelligence (Master of Science)
   (Po-Vers. 2021s | TechFak | Artificial Intelligence (Master of Science) | Gesamtkonto | Nebenfach | Nebenfach Mathematik | 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