International Center for Computational Logic - Benutzerbeiträge [de]

Inproceedings3463

2026-03-11T10:05:04Z

Sergei Obiedkov:

{{Publikation Erster Autor
|ErsterAutorVorname=Sergei
|ErsterAutorNachname=Obiedkov
|FurtherAuthors=Barış Sertkaya
}}
{{Inproceedings
|Referiert=1
|Title=AFCA: Searching for Complete Extensions via Enumeration of a Closure System
|To appear=0
|Year=2026
|Booktitle=Solver and Benchmark Descriptions of ICCMA 2025: Sixth International Competition on Computational Models of Argumentation
|Pages=11–12
|Editor=Iosif Apostolakis, Andrei Popesci, Johannes P. Wallner
}}
{{Publikation Details
|Abstract=AFCA is a solver for abstract argumentation that operates by enumerating closed sets. Unlike most other solvers, it does not rely on SAT or CSP solvers. Instead, AFCA adapts algorithms from formal concept analysis used for enumerating closed sets of a closure system. While the system supports several semantics, this paper focuses on the algorithm used for credulous acceptance under complete semantics. The approach is based on enumerating subsets of arguments that are semicomplete—that is, conflict-free sets containing all the arguments they defend. We show that semicomplete sets form a closure system, and we leverage this property to design a targeted enumeration algorithm. In contrast to generic enumeration, our method reduces the search space by dynamically selecting relevant defenders and pruning infeasible branches.
|Download=Iccma25.pdf
|Link=https://www.argumentationcompetition.org/2025/iccma-25-proceedings.pdf#page=11
|Projekt=ScaDS.AI
|Forschungsgruppe=Wissensbasierte Systeme
|BibTex=@article{obiedkov2025afca,
title={AFCA: Searching for Complete Extensions via Enumeration of a Closure System},
author={Obiedkov, Sergei and Sertkaya, Bar{\i}s},
journal={ICCMA 2025},
pages={11}
}@article{obiedkov2025afca,
title={AFCA: Searching for Complete Extensions via Enumeration of a Closure System},
author={Obiedkov, Sergei and Sertkaya, Bar{\i}s},
journal={ICCMA 2025},
pages={11--12}
}
}}

Inproceedings3463

2026-03-11T10:02:36Z

Sergei Obiedkov: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Sergei |ErsterAutorNachname=Obiedkov |FurtherAuthors=Barış Sertkaya }} {{Inproceedings |Referiert=1 |Title=AFCA: Searching for Complete Extensions via Enumeration of a Closure System |To appear=0 |Year=2025 |Booktitle=Solver and Benchmark Descriptions of ICCMA 2025: Sixth International Competition on Computational Models of Argumentation |Pages=11–12 |Editor=Iosif Apostolakis, Andrei Popesci, Johannes P.…“

{{Publikation Erster Autor
|ErsterAutorVorname=Sergei
|ErsterAutorNachname=Obiedkov
|FurtherAuthors=Barış Sertkaya
}}
{{Inproceedings
|Referiert=1
|Title=AFCA: Searching for Complete Extensions via Enumeration of a Closure System
|To appear=0
|Year=2025
|Booktitle=Solver and Benchmark Descriptions of ICCMA 2025: Sixth International Competition on Computational Models of Argumentation
|Pages=11–12
|Editor=Iosif Apostolakis, Andrei Popesci, Johannes P. Wallner
}}
{{Publikation Details
|Abstract=AFCA is a solver for abstract argumentation that operates by enumerating closed sets. Unlike most other solvers, it does not rely on SAT or CSP solvers. Instead, AFCA adapts algorithms from formal concept analysis used for enumerating closed sets of a closure system. While the system supports several semantics, this paper focuses on the algorithm used for credulous acceptance under complete semantics. The approach is based on enumerating subsets of arguments that are semicomplete—that is, conflict-free sets containing all the arguments they defend. We show that semicomplete sets form a closure system, and we leverage this property to design a targeted enumeration algorithm. In contrast to generic enumeration, our method reduces the search space by dynamically selecting relevant defenders and pruning infeasible branches.
|Download=Iccma25.pdf
|Link=https://www.argumentationcompetition.org/2025/iccma-25-proceedings.pdf#page=11
|Projekt=ScaDS.AI
|Forschungsgruppe=Wissensbasierte Systeme
|BibTex=@article{obiedkov2025afca,
title={AFCA: Searching for Complete Extensions via Enumeration of a Closure System},
author={Obiedkov, Sergei and Sertkaya, Bar{\i}s},
journal={ICCMA 2025},
pages={11}
}@article{obiedkov2025afca,
title={AFCA: Searching for Complete Extensions via Enumeration of a Closure System},
author={Obiedkov, Sergei and Sertkaya, Bar{\i}s},
journal={ICCMA 2025},
pages={11--12}
}
}}

Datei:Iccma25.pdf

2026-03-11T10:01:27Z

Sergei Obiedkov:

Article3120

2026-02-24T10:09:14Z

Sergei Obiedkov: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Ramil |ErsterAutorNachname=Yarullin |FurtherAuthors=Sergei Obiedkov }} {{Article |Referiert=1 |Title=From equivalence queries to PAC learning: The case of implication theories |To appear=0 |Year=2020 |Month=Dezember |Journal=International Journal of Approximate Reasoning |Volume=127 |Pages=1–16 |Publisher=Elsevier }} {{Publikation Details |Abstract=In Angluin's exact-learning framework, equivalence queries…“

{{Publikation Erster Autor
|ErsterAutorVorname=Ramil
|ErsterAutorNachname=Yarullin
|FurtherAuthors=Sergei Obiedkov
}}
{{Article
|Referiert=1
|Title=From equivalence queries to PAC learning: The case of implication theories
|To appear=0
|Year=2020
|Month=Dezember
|Journal=International Journal of Approximate Reasoning
|Volume=127
|Pages=1–16
|Publisher=Elsevier
}}
{{Publikation Details
|Abstract=In Angluin's exact-learning framework, equivalence queries can be simulated by stochastic equivalence testing to achieve a probably approximately correct identification of an unknown concept. We present an analysis of the number of samples that need to be generated in the process leading to a theoretical improvement on an earlier approach. We apply this modification to a previously known probably approximately correct algorithm for computing implication bases with an implication oracle and evaluate its performance in terms of the number of queries to the oracle on artificial and real-world data.
|Download=Paper journal approx reasoning v4.pdf
|Link=https://www.sciencedirect.com/science/article/pii/S0888613X20302176
|DOI Name=10.1016/j.ijar.2020.08.011
|Forschungsgruppe=Wissensbasierte Systeme
|BibTex=@article{YARULLIN20201,
title = {From equivalence queries to PAC learning: The case of implication theories},
journal = {International Journal of Approximate Reasoning},
volume = {127},
pages = {1-16},
year = {2020},
issn = {0888-613X},
doi = {https://doi.org/10.1016/j.ijar.2020.08.011},
url = {https://www.sciencedirect.com/science/article/pii/S0888613X20302176},
author = {Ramil Yarullin and Sergei Obiedkov},
keywords = {Attribute exploration, Concept learning, Formal concept analysis, Implications, PAC learning, Query learning},
abstract = {In Angluin's exact-learning framework, equivalence queries can be simulated by stochastic equivalence testing to achieve a probably approximately correct identification of an unknown concept. We present an analysis of the number of samples that need to be generated in the process leading to a theoretical improvement on an earlier approach. We apply this modification to a previously known probably approximately correct algorithm for computing implication bases with an implication oracle and evaluate its performance in terms of the number of queries to the oracle on artificial and real-world data.}
}
}}

Datei:Paper journal approx reasoning v4.pdf

2026-02-24T10:08:11Z

Sergei Obiedkov:

Techreport3062

2026-02-24T10:04:14Z

Sergei Obiedkov: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Nikita |ErsterAutorNachname=Remnev |FurtherAuthors=Sergei Obiedkov; Ekaterina Rakhilina; Ivan Smirnov; Anastasia Vyrenkova }} {{Techreport |Title=A Language Model for Grammatical Error Correction in L2 Russian |Year=2023 |Institution=arXiv.org |Archivierungsnummer=arXiv:2307.01609 }} {{Publikation Details |Abstract=Grammatical error correction is one of the fundamental tasks in Natural Language Processing. Fo…“

{{Publikation Erster Autor
|ErsterAutorVorname=Nikita
|ErsterAutorNachname=Remnev
|FurtherAuthors=Sergei Obiedkov; Ekaterina Rakhilina; Ivan Smirnov; Anastasia Vyrenkova
}}
{{Techreport
|Title=A Language Model for Grammatical Error Correction in L2 Russian
|Year=2023
|Institution=arXiv.org
|Archivierungsnummer=arXiv:2307.01609
}}
{{Publikation Details
|Abstract=Grammatical error correction is one of the fundamental tasks in Natural Language Processing. For the Russian language, most of the spellcheckers available correct typos and other simple errors with high accuracy, but often fail when faced with non-native (L2) writing, since the latter contains errors that are not typical for native speakers. In this paper, we propose a pipeline involving a language model intended for correcting errors in L2 Russian writing. The language model proposed is trained on untagged texts of the Newspaper subcorpus of the Russian National Corpus, and the quality of the model is validated against the RULEC-GEC corpus.
|Download=2307.01609v1.pdf
|Link=https://arxiv.org/abs/2307.01609
|DOI Name=10.48550/arXiv.2307.01609
|Forschungsgruppe=Wissensbasierte Systeme
}}

Datei:2307.01609v1.pdf

2026-02-24T10:03:20Z

Sergei Obiedkov:

Inproceedings3460

2026-02-24T09:55:27Z

Sergei Obiedkov:

{{Publikation Erster Autor
|ErsterAutorVorname=Sergei
|ErsterAutorNachname=Obiedkov
|FurtherAuthors=Barış Sertkaya
}}
{{Inproceedings
|Referiert=1
|Title=PAC Learning of Concept Inclusions for Ontology-Mediated Query Answering (Extended Abstract)
|To appear=0
|Year=2025
|Month=September
|Booktitle=DL 2025: 38th International Workshop on Description Logics
|Publisher=CEUR Workshop Proceedings
|Editor=Lidia Tendera, Yazmin Ibanez Garcia, Patrick Koopmann
|Volume=4091
}}
{{Publikation Details
|ISSN=1613-0073
|Download=Paper27.pdf
|Link=https://ceur-ws.org/Vol-4091/paper27.pdf
|Projekt=ScaDS.AI
|Forschungsgruppe=Wissensbasierte Systeme
}}

Inproceedings3460

2026-02-24T09:54:11Z

Sergei Obiedkov: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Sergei |ErsterAutorNachname=Obiedkov |FurtherAuthors=Barış Sertkaya }} {{Inproceedings |Referiert=1 |Title=PAC Learning of Concept Inclusions for Ontology- Mediated Query Answering (Extended Abstract) |To appear=0 |Year=2025 |Month=September |Booktitle=DL 2025: 38th International Workshop on Description Logics |Publisher=CEUR Workshop Proceedings |Editor=Lidia Tendera, Yazmin Ibanez Garcia, Patrick Koopmann…“

{{Publikation Erster Autor
|ErsterAutorVorname=Sergei
|ErsterAutorNachname=Obiedkov
|FurtherAuthors=Barış Sertkaya
}}
{{Inproceedings
|Referiert=1
|Title=PAC Learning of Concept Inclusions for Ontology- Mediated Query Answering (Extended Abstract)
|To appear=0
|Year=2025
|Month=September
|Booktitle=DL 2025: 38th International Workshop on Description Logics
|Publisher=CEUR Workshop Proceedings
|Editor=Lidia Tendera, Yazmin Ibanez Garcia, Patrick Koopmann
|Volume=4091
}}
{{Publikation Details
|ISSN=1613-0073
|Download=Paper27.pdf
|Link=https://ceur-ws.org/Vol-4091/paper27.pdf
|Projekt=ScaDS.AI
|Forschungsgruppe=Wissensbasierte Systeme
}}

Datei:Paper27.pdf

2026-02-24T09:53:45Z

Sergei Obiedkov:

Inproceedings3459

2026-02-24T09:41:02Z

Sergei Obiedkov: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Sergei |ErsterAutorNachname=Obiedkov |FurtherAuthors=Barış Sertkaya }} {{Inproceedings |Referiert=1 |Title=Probably Approximately Correct Ontology Completion with pacco (Extended Abstract) |To appear=0 |Year=2024 |Month=Juni |Booktitle=DL 2024: 37th International Workshop on Description Logics |Publisher=CEUR Workshop Proceedings |Editor=Laura Giordano, Jean Christoph Jung, Ana Ozaki |Volume=3739 }} {{Publ…“

{{Publikation Erster Autor
|ErsterAutorVorname=Sergei
|ErsterAutorNachname=Obiedkov
|FurtherAuthors=Barış Sertkaya
}}
{{Inproceedings
|Referiert=1
|Title=Probably Approximately Correct Ontology Completion with pacco (Extended Abstract)
|To appear=0
|Year=2024
|Month=Juni
|Booktitle=DL 2024: 37th International Workshop on Description Logics
|Publisher=CEUR Workshop Proceedings
|Editor=Laura Giordano, Jean Christoph Jung, Ana Ozaki
|Volume=3739
}}
{{Publikation Details
|ISSN=1613-0073
|Download=Abstract7.pdf
|Link=https://ceur-ws.org/Vol-3739/abstract-20.pdf
|Projekt=ScaDS.AI
|Forschungsgruppe=Wissensbasierte Systeme
}}

Datei:Abstract7.pdf

2026-02-24T09:40:15Z

Sergei Obiedkov:

Inproceedings3458

2026-02-24T09:32:55Z

Sergei Obiedkov: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Bernhard |ErsterAutorNachname=Ganter |FurtherAuthors=Tom Hanika; Johannes Hirth; Sergei Obiedkov }} {{Inproceedings |Referiert=1 |Title=Collaborative Hybrid Human AI Learning through Conceptual Exploration |To appear=0 |Year=2024 |Month=Juni |Booktitle=HHAI-WS 2024: Workshops at the Third International Conference on Hybrid Human-Artificial Intelligence (HHAI 2024) |Pages=1–8 |Publisher=CEUR Workshop Proceed…“

{{Publikation Erster Autor
|ErsterAutorVorname=Bernhard
|ErsterAutorNachname=Ganter
|FurtherAuthors=Tom Hanika; Johannes Hirth; Sergei Obiedkov
}}
{{Inproceedings
|Referiert=1
|Title=Collaborative Hybrid Human AI Learning through Conceptual Exploration
|To appear=0
|Year=2024
|Month=Juni
|Booktitle=HHAI-WS 2024: Workshops at the Third International Conference on Hybrid Human-Artificial Intelligence (HHAI 2024)
|Pages=1–8
|Publisher=CEUR Workshop Proceedings
|Editor=Petter Ericson, Nina Khairova, Marina De Vos
|Volume=3825
}}
{{Publikation Details
|Abstract=Conceptual Exploration is a sophisticated method for the interactive and structured acquisition of knowledge from experts. It is therefore particularly suitable for the use in hybrid settings where both humans and AIs act as experts. This article provides a brief summary of how conceptual exploration can be used in the context of Hybrid Human AI systems, as discussed within a tutorial during the third HHAI conference in Malmö, Sweden. We will recapitulate two small experiments that were carried out with the participants of the tutorial and their results. Finally, we give some pointers on how this promising link can be further researched.
|ISSN=1613-0073
|Download=Tutorial.pdf
|Link=https://ceur-ws.org/Vol-3825/tutorial.pdf
|Projekt=ScaDS.AI
|Forschungsgruppe=Wissensbasierte Systeme
}}

Datei:Tutorial.pdf

2026-02-24T09:32:02Z

Sergei Obiedkov:

Proceedings3029

2026-02-24T09:20:45Z

Sergei Obiedkov:

{{Publikation Erster Autor
|ErsterAutorVorname=Inma P.
|ErsterAutorNachname=Cabrera
|FurtherAuthors=Sébastien Ferré; Sergei Obiedkov
}}
{{Proceedings
|Title=Conceptual Knowledge Structures
|To appear=0
|Year=2024
|Month=September
|Publisher=Springer
|Series=Lecture Notes in Computer Science
|Volume=14914
}}
{{Publikation Details
|Abstract=This book constitutes the proceedings of the First International Joint Conference on Conceptual Knowledge Structures, CONCEPTS 2024, which took place in Cádiz, Spain, during September 9-13, 2024. The conference is an amalgamation of the 18th International Conference on Formal Concept Analysis (ICFCA); the 17th International Conference on Concept Lattices and Their Applications (CLA); and the 28th International Conference on Conceptual Structures (ICCS).

The 18 full and 4 short papers included in this book were carefully reviewed and selected from 38 submissions. They were organized in topical sections as follows: theory; algorithms, methods, and resources; applications.
|ISBN=978-3-031-67867-7
|ISSN=0302-9743
|Link=https://link.springer.com/book/10.1007/978-3-031-67868-4
|DOI Name=10.1007/978-3-031-67868-4
|Projekt=SECAI
|Forschungsgruppe=Wissensbasierte Systeme
}}

Proceedings3029

2026-02-24T09:19:48Z

Sergei Obiedkov:

{{Publikation Erster Autor
|ErsterAutorVorname=Inma P.
|ErsterAutorNachname=Cabrera
|FurtherAuthors=Sébastien Ferré; Sergei Obiedkov
}}
{{Proceedings
|Title=Conceptual Knowledge Structures
|To appear=0
|Year=2024
|Month=September
|Publisher=Springer
|Series=Lecture Notes in Computer Science
|Volume=14914
}}
{{Publikation Details
|Abstract=This book constitutes the proceedings of the First International Joint Conference on Conceptual Knowledge Structures, CONCEPTS 2024, which took place in Cádiz, Spain, during September 9-13, 2024. The conference is an amalgamation of the 18th International Conference on Formal Concept Analysis (ICFCA); the 17th International Conference on Concept Lattices and Their Applications (CLA); and the 28th International Conference on Conceptual Structures (ICCS).

The 18 full and 4 short papers included in this book were carefully reviewed and selected from 38 submissions. They were organized in topical sections as follows: Theory; algorithms, methods, and resources; applications.
|ISBN=978-3-031-67867-7
|ISSN=0302-9743
|Link=https://link.springer.com/book/10.1007/978-3-031-67868-4
|DOI Name=10.1007/978-3-031-67868-4
|Projekt=SECAI
|Forschungsgruppe=Wissensbasierte Systeme
}}

Proceedings3029

2026-02-24T09:19:10Z

Sergei Obiedkov: Die Seite wurde neu angelegt: „{{Publikation Erster Autor |ErsterAutorVorname=Inma P. |ErsterAutorNachname=Cabrera |FurtherAuthors=Sébastien Ferré; Sergei Obiedkov }} {{Proceedings |Title=Conceptual Knowledge Structures |To appear=0 |Year=2024 |Month=September |Publisher=Springer |Series=Lecture Notes in Computer Science |Volume=14914 }} {{Publikation Details |Abstract=This book constitutes the proceedings of the First International Joint Conference on Conceptual Knowledge Structures…“

{{Publikation Erster Autor
|ErsterAutorVorname=Inma P.
|ErsterAutorNachname=Cabrera
|FurtherAuthors=Sébastien Ferré; Sergei Obiedkov
}}
{{Proceedings
|Title=Conceptual Knowledge Structures
|To appear=0
|Year=2024
|Month=September
|Publisher=Springer
|Series=Lecture Notes in Computer Science
|Volume=14914
}}
{{Publikation Details
|Abstract=This book constitutes the proceedings of the First International Joint Conference on Conceptual Knowledge Structures, CONCEPTS 2024, which took place in Cádiz, Spain, during September 9-13, 2024. The conference is an amalgamation of the 18th International Conference on Formal Concept Analysis (ICFCA); the 17th International Conference on Concept Lattices and Their Applications (CLA); and the 28th International Conference on Conceptual Structures (ICCS).

The 18 full and 4 short papers included in this book were carefully reviewed and selected from 38 submissions. They were organized in topical sections as follows: Theory; algorithms, methods, and resources; applications.
|ISBN=978-3-031-67867-7
|ISSN=0302-9743
|Link=https://link.springer.com/book/10.1007/978-3-031-67868-4
|DOI Name=https://doi.org/10.1007/978-3-031-67868-4
|Projekt=SECAI
|Forschungsgruppe=Wissensbasierte Systeme
}}

Complexity Theory (WS2025)

2026-02-03T14:10:25Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch; Stephan Mennicke; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description====Examination Dates and Mode===

The registration and scheduling for exams depend on the module they are for. All students need to contact the [[Wissensbasierte_Systeme/en|KBS secretary]] to arrange time slots for their oral exams, or the secretary of another chair in the case of another main examiner. The preferred date for oral exams is '''24th February 2026'''. Although we cannot generally accommodate wishes for specific dates, students with justified time constraints during the examination period can still let us know as early as possible.

Students taking Complexity Theory as part of any '''other module''' should contact the secretary of the main examiner to find a date. If the main examiner is Markus Krötzsch, the preferred date will also be '''24th February 2026'''.

== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].

===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
|Download=CT2025-Lecture-17-overlay.pdf, CT2025-Lecture-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
|Download=CT2025-Lecture-18-overlay.pdf, CT2025-Lecture-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
|Download=CT2025-Exercise-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
|Download=CT2025-Lecture-19-overlay.pdf, CT2025-Lecture-19-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
|Download=CT2025-Lecture-20-overlay.pdf, CT2025-Lecture-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
|Download=CT2025-Lecture-21-overlay.pdf, CT2025-Lecture-21-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
|Download=CT2025-Lecture-22-overlay.pdf, CT2025-Lecture-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
|Download=CT2025-Exercise-08.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
|Download=CT2025-Lecture-23-overlay.pdf, CT2025-Lecture-23-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
|Download=CT2025-Lecture-24-overlay.pdf, CT2025-Lecture-24-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
|Download=CT2025-Exercise-09.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
|Download=CT2025-Lecture-25-overlay.pdf, CT2025-Lecture-25-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
|Download=CT2025-Lecture-26-overlay.pdf, CT2025-Lecture-26-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
|Download=Exercise-10.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Constant-Factor Approximations
|Room=APB E005
|Date=2026-01-26
|DS=DS4
|Download=CT2025-Lecture-27-overlay.pdf, CT2025-Lecture-27-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Approximation Schemes
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
|Download=CT2025-Lecture-28-overlay.pdf, CT2025-Lecture-28-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=All the Rest
|Room=APB E005
|Date=2026-01-27
|DS=DS5
|Download=CT2025-Exercise-11.pdf, CT2025-Exercise-11-5-slides.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Parameterized Complexity
|Room=APB E005
|Date=2026-02-02
|DS=DS4
|Download=CT2025-Lecture-29-overlay.pdf, CT2025-Lecture-29-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=no more exercise
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Datei:CT2025-Lecture-29-print.pdf

2026-02-03T14:10:21Z

Sergei Obiedkov:

Datei:CT2025-Lecture-29-overlay.pdf

2026-02-03T14:10:04Z

Sergei Obiedkov:

Complexity Theory (WS2025)

2026-01-30T16:08:43Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch; Stephan Mennicke; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description====Examination Dates and Mode===

The registration and scheduling for exams depend on the module they are for. All students need to contact the [[Wissensbasierte_Systeme/en|KBS secretary]] to arrange time slots for their oral exams, or the secretary of another chair in the case of another main examiner. The preferred date for oral exams is '''24th February 2026'''. Although we cannot generally accommodate wishes for specific dates, students with justified time constraints during the examination period can still let us know as early as possible.

Students taking Complexity Theory as part of any '''other module''' should contact the secretary of the main examiner to find a date. If the main examiner is Markus Krötzsch, the preferred date will also be '''24th February 2026'''.

== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].

===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
|Download=CT2025-Lecture-17-overlay.pdf, CT2025-Lecture-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
|Download=CT2025-Lecture-18-overlay.pdf, CT2025-Lecture-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
|Download=CT2025-Exercise-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
|Download=CT2025-Lecture-19-overlay.pdf, CT2025-Lecture-19-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
|Download=CT2025-Lecture-20-overlay.pdf, CT2025-Lecture-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
|Download=CT2025-Lecture-21-overlay.pdf, CT2025-Lecture-21-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
|Download=CT2025-Lecture-22-overlay.pdf, CT2025-Lecture-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
|Download=CT2025-Exercise-08.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
|Download=CT2025-Lecture-23-overlay.pdf, CT2025-Lecture-23-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
|Download=CT2025-Lecture-24-overlay.pdf, CT2025-Lecture-24-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
|Download=CT2025-Exercise-09.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
|Download=CT2025-Lecture-25-overlay.pdf, CT2025-Lecture-25-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
|Download=CT2025-Lecture-26-overlay.pdf, CT2025-Lecture-26-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
|Download=Exercise-10.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Constant-Factor Approximations
|Room=APB E005
|Date=2026-01-26
|DS=DS4
|Download=CT2025-Lecture-27-overlay.pdf, CT2025-Lecture-27-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Approximation Schemes
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
|Download=CT2025-Lecture-28-overlay.pdf, CT2025-Lecture-28-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=All the Rest
|Room=APB E005
|Date=2026-01-27
|DS=DS5
|Download=CT2025-Exercise-11.pdf, CT2025-Exercise-11-5-slides.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Parameterized Complexity
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=no more exercise
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Datei:CT2025-Lecture-28-print.pdf

2026-01-30T16:08:40Z

Sergei Obiedkov:

Datei:CT2025-Lecture-28-overlay.pdf

2026-01-30T16:08:26Z

Sergei Obiedkov:

Complexity Theory (WS2025)

2026-01-29T10:31:10Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch; Stephan Mennicke; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description====Examination Dates and Mode===

The registration and scheduling for exams depend on the module they are for. All students need to contact the [[Wissensbasierte_Systeme/en|KBS secretary]] to arrange time slots for their oral exams, or the secretary of another chair in the case of another main examiner. The preferred date for oral exams is '''24th February 2026'''. Although we cannot generally accommodate wishes for specific dates, students with justified time constraints during the examination period can still let us know as early as possible.

Students taking Complexity Theory as part of any '''other module''' should contact the secretary of the main examiner to find a date. If the main examiner is Markus Krötzsch, the preferred date will also be '''24th February 2026'''.

== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].

===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
|Download=CT2025-Lecture-17-overlay.pdf, CT2025-Lecture-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
|Download=CT2025-Lecture-18-overlay.pdf, CT2025-Lecture-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
|Download=CT2025-Exercise-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
|Download=CT2025-Lecture-19-overlay.pdf, CT2025-Lecture-19-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
|Download=CT2025-Lecture-20-overlay.pdf, CT2025-Lecture-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
|Download=CT2025-Lecture-21-overlay.pdf, CT2025-Lecture-21-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
|Download=CT2025-Lecture-22-overlay.pdf, CT2025-Lecture-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
|Download=CT2025-Exercise-08.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
|Download=CT2025-Lecture-23-overlay.pdf, CT2025-Lecture-23-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
|Download=CT2025-Lecture-24-overlay.pdf, CT2025-Lecture-24-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
|Download=CT2025-Exercise-09.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
|Download=CT2025-Lecture-25-overlay.pdf, CT2025-Lecture-25-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
|Download=CT2025-Lecture-26-overlay.pdf, CT2025-Lecture-26-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
|Download=Exercise-10.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Constant-Factor Approximations
|Room=APB E005
|Date=2026-01-26
|DS=DS4
|Download=CT2025-Lecture-27-overlay.pdf, CT2025-Lecture-27-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Approximation Schemes
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=All the Rest
|Room=APB E005
|Date=2026-01-27
|DS=DS5
|Download=CT2025-Exercise-11.pdf, CT2025-Exercise-11-5-slides.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Parameterized Complexity
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=no more exercise
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Datei:CT2025-Lecture-27-print.pdf

2026-01-29T10:31:04Z

Sergei Obiedkov:

Datei:CT2025-Lecture-27-overlay.pdf

2026-01-29T10:30:18Z

Sergei Obiedkov:

Datei:Exercise-10.pdf

2026-01-20T15:45:05Z

Sergei Obiedkov: Sergei Obiedkov lud eine neue Version von Datei:Exercise-10.pdf hoch

Complexity Theory (WS2025)

2026-01-19T21:09:35Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch; Stephan Mennicke; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description====Examination Dates and Mode===

The registration and scheduling for exams depend on the module they are for. All students need to contact the [[Wissensbasierte_Systeme/en|KBS secretary]] to arrange time slots for their oral exams, or the secretary of another chair in the case of another main examiner. The preferred date for oral exams is '''24th February 2026'''. Although we cannot generally accommodate wishes for specific dates, students with justified time constraints during the examination period can still let us know as early as possible.

Students taking Complexity Theory as part of any '''other module''' should contact the secretary of the main examiner to find a date. If the main examiner is Markus Krötzsch, the preferred date will also be '''24th February 2026'''.

== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].

===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
|Download=CT2025-Lecture-17-overlay.pdf, CT2025-Lecture-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
|Download=CT2025-Lecture-18-overlay.pdf, CT2025-Lecture-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
|Download=CT2025-Exercise-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
|Download=CT2025-Lecture-19-overlay.pdf, CT2025-Lecture-19-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
|Download=CT2025-Lecture-20-overlay.pdf, CT2025-Lecture-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
|Download=CT2025-Lecture-21-overlay.pdf, CT2025-Lecture-21-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
|Download=CT2025-Lecture-22-overlay.pdf, CT2025-Lecture-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
|Download=CT2025-Exercise-08.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
|Download=CT2025-Lecture-23-overlay.pdf, CT2025-Lecture-23-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
|Download=CT2025-Exercise-09.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
|Download=Exercise-10.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Constant-Factor Approximations
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Approximation Schemes
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Parameterized Complexity
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=TBA
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Datei:Exercise-10.pdf

2026-01-19T21:09:30Z

Sergei Obiedkov:

Datei:CT2025-Lecture-23-print.pdf

2026-01-12T19:27:57Z

Sergei Obiedkov: Sergei Obiedkov lud eine neue Version von Datei:CT2025-Lecture-23-print.pdf hoch

Datei:CT2025-Lecture-23-overlay.pdf

2026-01-12T19:27:38Z

Sergei Obiedkov: Sergei Obiedkov lud eine neue Version von Datei:CT2025-Lecture-23-overlay.pdf hoch

Complexity Theory (WS2025)

2026-01-12T19:22:38Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch; Stephan Mennicke; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description====Examination Dates and Mode===

The registration and scheduling for exams depend on the module they are for. All students need to contact the [[Wissensbasierte_Systeme/en|KBS secretary]] to arrange time slots for their oral exams, or the secretary of another chair in the case of another main examiner. The preferred date for oral exams is '''24th February 2026'''. Although we cannot generally accommodate wishes for specific dates, students with justified time constraints during the examination period can still let us know as early as possible.

Students taking Complexity Theory as part of any '''other module''' should contact the secretary of the main examiner to find a date. If the main examiner is Markus Krötzsch, the preferred date will also be '''24th February 2026'''.

== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].

===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
|Download=CT2025-Lecture-17-overlay.pdf, CT2025-Lecture-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
|Download=CT2025-Lecture-18-overlay.pdf, CT2025-Lecture-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
|Download=CT2025-Exercise-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
|Download=CT2025-Lecture-19-overlay.pdf, CT2025-Lecture-19-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
|Download=CT2025-Lecture-20-overlay.pdf, CT2025-Lecture-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
|Download=CT2025-Lecture-21-overlay.pdf, CT2025-Lecture-21-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
|Download=CT2025-Lecture-22-overlay.pdf, CT2025-Lecture-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
|Download=CT2025-Exercise-08.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
|Download=CT2025-Lecture-23-overlay.pdf, CT2025-Lecture-23-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
|Download=CT2025-Exercise-09.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Constant-Factor Approximations
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Approximation Schemes
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Parameterized Complexity
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=TBA
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Datei:CT2025-Lecture-23-print.pdf

2026-01-12T19:22:32Z

Sergei Obiedkov:

Datei:CT2025-Lecture-23-overlay.pdf

2026-01-12T19:22:16Z

Sergei Obiedkov:

Complexity Theory (WS2025)

2026-01-08T10:34:15Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch; Stephan Mennicke; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description====Examination Dates and Mode===

The registration and scheduling for exams depend on the module they are for. All students need to contact the [[Wissensbasierte_Systeme/en|KBS secretary]] to arrange time slots for their oral exams, or the secretary of another chair in the case of another main examiner. The preferred date for oral exams is '''24th February 2026'''. Although we cannot generally accommodate wishes for specific dates, students with justified time constraints during the examination period can still let us know as early as possible.

Students taking Complexity Theory as part of any '''other module''' should contact the secretary of the main examiner to find a date. If the main examiner is Markus Krötzsch, the preferred date will also be '''24th February 2026'''.

== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].

===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
|Download=CT2025-Lecture-17-overlay.pdf, CT2025-Lecture-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
|Download=CT2025-Lecture-18-overlay.pdf, CT2025-Lecture-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
|Download=CT2025-Exercise-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
|Download=CT2025-Lecture-19-overlay.pdf, CT2025-Lecture-19-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
|Download=CT2025-Lecture-20-overlay.pdf, CT2025-Lecture-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
|Download=CT2025-Lecture-21-overlay.pdf, CT2025-Lecture-21-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
|Download=CT2025-Lecture-22-overlay.pdf, CT2025-Lecture-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
|Download=CT2025-Exercise-08.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems (1)
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Constant-Factor Approximations
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Approximation Schemes
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Parameterized Complexity
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=TBA
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Complexity Theory (WS2025)

2026-01-08T10:30:48Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Markus Krötzsch; Stephan Mennicke; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description====Examination Dates and Mode===

The registration and scheduling for exams depend on the module they are for. All students need to contact the [[Wissensbasierte_Systeme/en|KBS secretary]] to arrange time slots for their oral exams, or the secretary of another chair in the case of another main examiner. The preferred date for oral exams is '''24th February 2026'''. Although we cannot generally accommodate wishes for specific dates, students with justified time constraints during the examination period can still let us know as early as possible.

Students taking Complexity Theory as part of any '''other module''' should contact the secretary of the main examiner to find a date. If the main examiner is Markus Krötzsch, the preferred date will also be '''24th February 2026'''.

== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].

===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
|Download=CT2025-Lecture-17-overlay.pdf, CT2025-Lecture-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
|Download=CT2025-Lecture-18-overlay.pdf, CT2025-Lecture-18-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
|Download=CT2025-Exercise-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
|Download=CT2025-Lecture-19-overlay.pdf, CT2025-Lecture-19-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
|Download=CT2025-Lecture-20-overlay.pdf, CT2025-Lecture-20-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
|Download=CT2025-Lecture-21-overlay.pdf, CT2025-Lecture-21-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
|Download=CT2025-Lecture-22-overlay.pdf, CT2025-Lecture-22-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
|Download=CT2025-Exercise-08.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems (1)
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=TBA
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Datei:CT2025-Lecture-22-print.pdf

2026-01-08T10:30:43Z

Sergei Obiedkov:

Datei:CT2025-Lecture-22-overlay.pdf

2026-01-08T10:30:29Z

Sergei Obiedkov:

Datei:CT2025-Lecture-21-print.pdf

2026-01-08T10:30:09Z

Sergei Obiedkov:

Datei:CT2025-Lecture-21-overlay.pdf

2026-01-08T10:29:55Z

Sergei Obiedkov:

Complexity Theory (WS2025)

2025-12-09T09:00:34Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Stephan Mennicke; Markus Krötzsch; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description=== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].


===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
|Download=CT2025-Lecture-17-overlay.pdf, CT2025-Lecture-17-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Hierarchy / Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
|Download=CT2025-Exercise-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems (1)
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=TBA
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Datei:CT2025-Lecture-17-print.pdf

2025-12-09T09:00:29Z

Sergei Obiedkov:

Datei:CT2025-Lecture-17-overlay.pdf

2025-12-09T09:00:16Z

Sergei Obiedkov:

Complexity Theory (WS2025)

2025-12-04T16:53:49Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Stephan Mennicke; Markus Krötzsch; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description=== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].


===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Hierarchy / Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-13
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems (1)
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=TBA
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Complexity Theory (WS2025)

2025-12-04T16:51:24Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Stephan Mennicke; Markus Krötzsch; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description=== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].


===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Hierarchy / Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-06
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-13
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems (1)
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing (3)
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Complexity Theory (WS2025)

2025-12-04T16:49:23Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Stephan Mennicke; Markus Krötzsch; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description=== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].


===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Hierarchy / Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2026-01-06
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-13
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems (1)
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing (3)
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Complexity Theory (WS2025)

2025-12-03T10:11:42Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Stephan Mennicke; Markus Krötzsch; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description=== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].


===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
|Download=CT2025-Lecture-14-overlay.pdf, CT2025-Lecture-14-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
|Download=CT2025-Lecture-15-overlay.pdf, CT2025-Lecture-15-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
|Download=CT2025-Lecture-16-overlay.pdf, CT2025-Lecture-16-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
|Download=CT2025-Exercise-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Hierarchy / Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Diagonalisation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2026-01-06
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-13
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems (1)
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing (3)
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}

Datei:CT2025-Lecture-16-print.pdf

2025-12-03T10:11:36Z

Sergei Obiedkov:

Datei:CT2025-Lecture-16-overlay.pdf

2025-12-03T10:11:15Z

Sergei Obiedkov:

Complexity Theory (WS2025)

2025-11-24T18:34:37Z

Sergei Obiedkov:

{{Vorlesung
|Title=Complexity Theory
|Research group=Wissensbasierte Systeme
|Lecturers=Stephan Mennicke; Markus Krötzsch; Sergei Obiedkov
|Term=WS
|Year=2025
|Lecture series=Complexity Theory
|Matrix=#complexity:tu-dresden.de
|Module=CMS-LM-ADV, CMS-LM-MOC, INF-25-MA-FTK-CT, INF-B-510, INF-B-520, INF-BAS6, INF-VERT6, MCL-KR, MCL-PI, MCL-TCSL
|SWSLecture=4
|SWSExercise=2
|SWSPractical=0
|Exam type=mündliche Prüfung
|Description=== Contents ==
This course covers both fundamental concepts and advanced topics in complexity theory.

Key topics are:
* '''Turing Machines (revision):''' Definition of Turing Machines; Variants; Computational Equivalence; Decidability and Recognizability; Enumeration
* '''Undecidability:''' Examples of Undecidable Problems; Mapping Reductions; Rice’s Theorem (both for characterizing Decidability and Recognizability); Recursion Theorem; Outlook into Decidability in Logic
* '''Time Complexity:''' Measuring Time Complexity; Many-One Reductions; Cook-Levin Theorem; Time Complexity Classes (P, NP, ExpTime); NP-completeness; pseudo-NP-complete problems
* '''Space Complexity:''' Space Complexity Classes (PSpace, L, NL); Savitch’s Theorem; PSpace-completeness; NL-completeness; NL = coNL
* '''Diagonalization:''' Hierarchy Theorems (det. Time, non-det. Time, Space); Gap Theorem; Ladner’s Theorem; Relativization; Baker-Gill-Solovay Theorem
* '''Alternation:''' Alternating Turing Machines; APTime = PSpace; APSpace = ExpTime; Polynomial Hierarchy 
* '''Circuit Complexity:''' Boolean Circuits; Alternative Proof of Cook-Levin Theorem; Parallel Computation (NC); P-completeness; P/poly; (Karp-Lipton Theorem, Meyer’s Theorem)
* '''Probabilistic Computation:''' Randomized Complexity Classes (RP, PP, BPP, ZPP); Sipser-Gács-Lautemann Theorem
* '''Quantum Computing:''' Quantum circuits, BQP, some basic results

===Mode of Teaching and Registration===

The course generally does not require a special registration, and there is no participant limit. However, students in programmes that use the Selma system (esp., students in CMS Master) will need to register there to obtain credits. 
Most of the materials will be freely available worldwide.

===Schedule and Location===

This page will publish all dates (see ''Dates & Materials'' above).
* The weekly lecture sessions will take place on Mondays DS4 (13.00 - 14.30) in [[APB E005]] and Tuesdays DS3 (11.10 - 12.40) in [[MER 0E23]].
* The weekly exercise session will take place on '''Tuesday DS5 (14.50 - 16.20)''', also in [[APB E005]].


===Contact===

Besides the regular meetings in lectures and exercise classes, you can also contact the teachers and other students in the public discussion channel on Matrix shown on the side.

===Acknowledgements===

The slides for some of the foundational lectures of this course are based on slides used by Markus Krötzsch for the course ''Complexity Theory'' at the University of Oxford, which were adopted from slides created by [http://logic.las.tu-berlin.de/Members/Kreutzer/ Stefan Kreutzer] and [http://www.cs.ox.ac.uk/people/ian.horrocks/ Ian Horrocks] for that course.

Further material has been prepared first by [[Daniel Borchmann/en|Daniel Borchmann]] during his time at TU Dresden.
|Literature=* '''Michael Sipser: ''Introduction to the Theory of Computation, International Edition''; 3rd Edition; Cengage Learning 2013'''
:: Introductory text that covers all basic topics in this lecture.

* Erich Grädel: ''Complexity Theory''; Lecture Notes, Winter Term 2009/10. Available online at https://logic.rwth-aachen.de/Teaching/KTQC-WS09/index.html.en
:: Free lecture notes with a general overview of main results; more detailed than Sipser on oracles and alternation; main reference for randomized computation

* John E. Hopcroft and Jeffrey D. Ullman: ''Introduction to Automata Theory, Languages, and Computation''; Addison Wesley Publishing Company 1979
:: The ''Cinderella Book''; contains a lot of information not contained in most other books; the hierarchy of undecidable problems as well as Rice' characterization of recognizable properties of recognizable languages are from here.

* Christos H. Papadimitriou: ''Computational Complexity''; 1995 Addison-Wesley Publishing Company, Inc
:: Standard reference text for many advanced aspects on complexity theory; the proofs of the Linear Speedup Theorem, the Gap Theorem, and Ladner's Theorem as given in the lecture are from here

* Sanjeev Arora and Boaz Barak: ''Computational Complexity: A Modern Approach''; Cambridge University Press 2009
:: Extensive book covering the state of the art of Complexity Theory

* Michael R. Garey and David S. Johnson: ''Computers and Intractability''; Bell Telephone Laboratories, Inc. 1979
:: The classical book on Complexity Theory; contains a long list of problems with their complexities


}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Introduction and Motivation
|Room=APB E005
|Date=2025-10-13
|DS=DS4
|Download=CT2025-Lecture-01-overlay.pdf, CT2025-Lecture-01-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Turing Machines and Languages
|Room=MER 0E23
|Date=2025-10-14
|DS=DS3
|Download=CT2025-Lecture-02-overlay.pdf, CT2025-Lecture-02-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-20
|DS=DS4
|Download=CT2025-Lecture-03-overlay.pdf, CT2025-Lecture-03-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Undecidability and Recursion
|Room=MER 0E23
|Date=2025-10-21
|DS=DS3
|Download=CT2025-Lecture-04-overlay.pdf, CT2025-Lecture-04-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Mathematical Foundations, Decidability, and Recognisability
|Room=APB E005
|Date=2025-10-21
|DS=DS5
|Download=CT2025-Exercise-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Time Complexity and Polynomial Time
|Room=APB E005
|Date=2025-10-27
|DS=DS4
|Download=CT2025-Lecture-05-overlay.pdf, CT2025-Lecture-05-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial-Time Reductions and Nondeterministic Polynomial Time
|Room=MER 0E23
|Date=2025-10-28
|DS=DS3
|Download=CT2025-Lecture-06-overlay.pdf, CT2025-Lecture-06-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Undecidability
|Room=APB E005
|Date=2025-10-28
|DS=DS5
|Download=CT2025-Exercise-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-03
|DS=DS4
|Download=CT2025-Lecture-07-overlay.pdf, CT2025-Lecture-07-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=NP-Complete Problems
|Room=MER 0E23
|Date=2025-11-04
|DS=DS3
|Download=CT2025-Lecture-08-overlay.pdf, CT2025-Lecture-08-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time Complexity
|Room=APB E005
|Date=2025-11-04
|DS=DS5
|Download=CT2025-Exercise-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Complexity and PSPACE
|Room=APB E005
|Date=2025-11-10
|DS=DS4
|Download=CT2025-Lecture-09-overlay.pdf, CT2025-Lecture-09-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Space and Games
|Room=MER 0E23
|Date=2025-11-11
|DS=DS3
|Download=CT2025-Lecture-10-overlay.pdf, CT2025-Lecture-10-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=NP-Completeness
|Room=APB E005
|Date=2025-11-11
|DS=DS5
|Download=CT2025-Exercise-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Logarithmic Space
|Room=APB E005
|Date=2025-11-17
|DS=DS4
|Download=CT2025-Lecture-11-overlay.pdf, CT2025-Lecture-11-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Hierarchy Theorems
|Room=MER 0E23
|Date=2025-11-18
|DS=DS3
|Download=CT2025-Lecture-12-overlay.pdf, CT2025-Lecture-12-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=More NP-Completeness and P-Completeness
|Room=APB E005
|Date=2025-11-18
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Space Hierarchy and Gaps
|Room=APB E005
|Date=2025-11-24
|DS=DS4
|Download=CT2025-Lecture-13-overlay.pdf, CT2025-Lecture-13-print.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP: Ladner's Theorem
|Room=MER 0E23
|Date=2025-11-25
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Space Complexity
|Room=APB E005
|Date=2025-11-25
|DS=DS5
|Download=CT2025-Exercise-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=P vs. NP and Diagonalisation
|Room=APB E005
|Date=2025-12-01
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Alternation
|Room=MER 0E23
|Date=2025-12-02
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Time and Space Complexity
|Room=APB E005
|Date=2025-12-02
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=The Polynomial Hierarchy
|Room=APB E005
|Date=2025-12-08
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Polynomial Hierarchy / Circuit Complexity
|Room=MER 0E23
|Date=2025-12-09
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Diagonalisation
|Room=APB E005
|Date=2025-12-09
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Circuits and Parallel Computation
|Room=APB E005
|Date=2025-12-15
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Questions and Answers (before Christmas)
|Room=MER 0E23
|Date=2025-12-16
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Christmas Break
|Room=APB E005
|Date=2025-12-16
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Turing Machines
|Room=APB E005
|Date=2026-01-05
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (1)
|Room=MER 0E23
|Date=2026-01-06
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Alternation
|Room=APB E005
|Date=2026-01-06
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Probabilistic Complexity Classes (2)
|Room=APB E005
|Date=2026-01-12
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (1)
|Room=MER 0E23
|Date=2026-01-13
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Polynomial Hierarchy
|Room=APB E005
|Date=2026-01-13
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Quantum Computing (2)
|Room=APB E005
|Date=2026-01-19
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Interactive Proof Systems (1)
|Room=MER 0E23
|Date=2026-01-20
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Circuit Complexity
|Room=APB E005
|Date=2026-01-20
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-01-26
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=MER 0E23
|Date=2026-01-27
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Randomised Computation
|Room=APB E005
|Date=2026-01-27
|DS=DS5
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=TBA
|Room=APB E005
|Date=2026-02-02
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=Summary and Consultation
|Room=MER 0E23
|Date=2026-02-03
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Übung
|Title=Quantum Computing (3)
|Room=APB E005
|Date=2026-02-03
|DS=DS5
}}