|
Die folgenden Informationen sind noch nicht freigegeben und deshalb unverbindlich: Complexity Theory SemesterWiSe 2026 / 27 Lecturer Gorav Jindal, Cornelius Brand (FIDS) Type of course (Veranstaltungsart) Vorlesung German title Komplexitätstheorie Contents The lecture and lab "Complexity Theory" cover computational complexity theory, the subfield of theoretical computer science that aims at proving lower bounds on the resources (e.g., time and memory) required for solving computational problems. Concrete topics in this course include: - Time and space hierarchy theorems via diagonalization? - Advanced aspects of NP-completeness (e.g., Ladner’s theorem) - Space complexity (L, NL, PSPACE)? - The polynomial-time hierarchy and complete problems for its levels - Communication complexity? - Circuit complexity? - Randomness and derandomization? - Algebraic models of computation Both introductory and advanced topics are covered in this course. After completing the lecture and lab "Complexity Theory", students are able to use diagonalization to demonstrate separations arising from different resource bounds. They have deeper insights into the connections between P and NP and can give advanced arguments for these connections. They are able to compare the complexity classes L, NL, and PSPACE, prove their interrelationships and identify complete problems for these classes. Going beyond the class NP, they are also able to explain the structure of the polynomial-time hierarchy, recognize problems complete for various levels of the hierarchy via polynomial-time reductions, and analyze the consequences of a collapse of this hierarchy. They explore how to exploit randomness as a resource in algorithms and assess techniques and limitations in derandomization. Complementing the classical Turing machine model of computation, students are moreover able to precisely quantify the amount of information exchange required for solving problems. They can investigate the role and limitations of circuit complexity in computational complexity. Finally, they are able to cast computational problems into algebraic models of computation and analyze their connections to classical Boolean models of computation. Recommended previous knowledge None, however basic knowledge of Theoretical Computer Science (see INF-BSc-P01), Algorithms and Data Structures (see INF-BSc-P08). Time/Date Mo 12 - 14; Exercise: Tue 12-14; Wed 12-14 Location BA.V03 Course homepage https://elearning.uni-regensburg.de/course/view.php?id=76387 (Disclaimer: Dieser Link wurde automatisch erzeugt und ist evtl. extern) Registration
MV, Wahlbereich ECTS 6 |