# Komplexitätstheorie

by Prof. Dr. rer. nat. Jürgen Dix ## Description

The first chapter covers some topics from the Chomsky hierarchy: the Myhill-Nerode theorem (how to construct a minimal finite automaton), deterministic PDAs, type 1 languages, normalform for type 0 and type 1 languages, Ehrenfeuchts theorem and Lindenmayer systems, a class of grammars that is orthogonal to parts of the Chomsky hierarchy.
Chapter 2 discusses undecidability results in greater depth (Posts Correspondence theorem, (primitive) recursive functions, Hilberts 10. problem (solving diophantine equations)). We also cover Rices theorem and its analogue for grammars. Makanins problem (word equations over a free monoid) is decidable but not primitive recursive.

Chapters 3 and 4 cover classical complexity results: time versus space, speed-up, gap-theorem, union-theorem and complexity classes: PH (the polynomial hierarchy), PSPACE, EXPSPACE and most of their interesting subclasses. We also cover closure properties and the Immerman/Szelepcsényi theorem.
Chapter 5 covers the arithmetical and analytical hierarchy (extending EXPSPACE into the undecidable) and discusses descriptive complexity: can we find logics corresponding to complexity classes (Fagins theorem).

4.2011

## Lecture recordings

04.Apr.201101:20:221.015
##### The Chomsky Hierarchy
1. The Chomsky Hierarchy: Definition 1.1 (Homomorphism), Definition 1.2 (Isomorphism), Lemma 1.3 (Unique Extension), Definition 1.4 ((Ext.) Regular Expressions Reg), Definition 1.5 (Semantics of Reg), Definition 1.6 (Deterministic Finite Automaton (dfa)). 1.1 Minimal DFA: Definition 1.7 (L), Definition 1.8 (RA), Lemma 1.9, Theorem 1.13 (Myhill-Nerode), Definition 1.14 (ML), Definition 1.15 (Morphisms between dfas), Theroem 1.16 (Minimality of ML), Definition 1.17 (Equivalence of states), Lemma 1.18 (Finite test set), Lemma 1.19. 1.2 cf = hom(Dyck reg): Definition 1.20 (Dycklanguage Dk), Theorem 1.21 (Closed under hom), Theorem 1.22 (CFL=h(Dyck reg)).
06.Apr.201101:35:17240
##### The Chomsky Hierarchy
1. The Chomsky Hierarchy: 1.2 cf = hom(Dyck reg): Definition 1.23 (Push-Down-Automaton (PDA)), Definition 1.24 (Accepted language of a PDA), Definition 1.25 (Configuration of a PDA), Definition 1.26 (Arbitrary computations Comp(M)), Theroem 1.27 (Comphalt(M)), Theroem 1.28 (Invalid TM computations as a CFL), Theorem 1.29 (Undecidability for CFL Problems), Theorem 1.30 (Valid Computations of a TM), Theorem 1.31 (Ogdens Lemma), Theorem 1.32 (Undecidability for CFL Problems), Lemma 1.33 (Decidable cf problems). 1.3 DPDA/DCFL: Definition 1.34 (DPDA), Theorem 1.35 (DCFL), Lemma 1.36 (DPDA without moves), Theorem 1.37 (DPDA do not hang), Lemma 1.39 (DCFL Regular = DCFL), Theorem 1.41 (Decidability of some DCFL problems), Theorem 1.42 (Undecidability of some DCFL problems), Theorem 1.43 (Senizergues, 1997)
11.Apr.201101:30:24202
##### The Chomsky Hierarchy
1. The Chomsky Hierarchy: Lemma 1.18 (Finite test set). 1.6 Ehrenfeucht: Definition 1.62, Example 1.63, Lemma 1.64 and 1.65, Lemma 1.66, Definition 1.67 (Test-Set), Lemma 1.68 (Test set for regular languages), Corollary 1.69 (Test set for regular languages), Theorem 1.70 (Test set for contextfree languages), Theorem 1.71 and Corollary 1.72, Theorem 1.73 (Test sets can not be computed), Definition 1.74, Definition 1.75 (Ehrenfeucht for word equations), Lemma 1.76 and 1.77
18.Apr.201134:37145
##### (Un-) Decidability
2. (Un-) Decidability: 2.2 PCP: Definition 2.5 (Correspondence system, PCP), Definition 2.6 (Variants of PCP), Beispiel 2.8, Lemma 2.9 (PCP over one alphabet), Theorem 2.10 (Undecidability of PCP)
18.Apr.201128:45101
##### (Un-) Decidability
2. (Un-) Decidability: 2.2 PCP: Theorem 2.10 (Undecidability of PCP), Lemma 2.11, 2.12, 2.13
18.Apr.201126:4992
##### The Chomsky Hierarchy and (Un-) Decidability
1. The Chomsky Hierarchy: 1.6 Ehrenfeucht: Lemma 1.64 and 1.65, Lemma 1.66 (Undecidability of f=L g). 2. (Un-) Decidability: 2.2 PCP: Theorem 2.10 (Undecidability of PCP), Lemma 2.11, 2.12, 2.13, Theorem 2.14 (Undecidability of various problems)
02.May.201101:39:42105
##### (Un-) Decidability
2. (Un-) Decidability: 2.2 PCP: Theorem 2.14 (Undecidability of various problems), Corollary 2.15 (Undecidability of various problems), The Domino-Problem, Theorem 2.16 ((Un-)Decidability of Plane Tiling), Domino-Problem for finite areas of the plane. 2.3 Makanins Algorithm: Example 2.17, Definition 2.18 (Word equations, solution), Theorem 2.19 (Makanin (1977)), Lemma 2.20 (Quadratic Equations), Example 2.21 (Illustration of Lemma 2.20)
09.May.201101:38:1797
##### (Un-) Decidability
2. (Un-) Decidability: 2.3 Makanins Algorithm: Lemma 2.20 (Quadratic Equations), Example 2.21 (Illustration of Lemma 2.20). 2.4 Recursive Functions: Definition 2.22 (Primitive recursive functions PR), Lemma 2.23 (More base functions), Lemma 2.24 (Modifying variables), Definition 2.25 and Lemma 2.26, Definition 2.27 and Lemma 2.28, Definition 2.29 (Simultaneous recursion), Definition 2.30 and Lemma 2.31, Lemma 2.32 (Coding Functions), Definition 2.33 (Ackermann and its Branches), Lemma 2.34 (Monotonicity of Ackermann), Definition 2.35 (Bounded operations), Definition 2.36 (Grzegorczyk Hierarchy), Theorem 2.37 (Growth), Corollary 2.38 (Grzegorczyk Hierarchy is strict), Example 2.39 (Fibonacci), Lemma 2.40, Theorem 2.41 (Grzegorczyk and primitive recursion), Definition 2.42 (Ackermann-Peter function), Lemma 2.43 (Minimal set of initial functions for PR)
16.May.201101:31:2787
##### (Un-) Decidability
2.4 Recursive Functions: Definition 2.42 (Ackermann-Peter function), Theorem 2.44 (PR = LOOP), Definition 2.45 (Operator), Definition 2.46 (recursive functions, R, Rpart), Theorem 2.47 (R = WHILE, Rpart = WHILEpart), Lemma 2.48 (Minimal set of initial functions for Rpart), Theorem 2.49 (Grzegorczyk and LOOP programs), Theorem 2.50 (R = TM, Rpart = TMpart). 2.5 Random Access Machines: Definition 2.51 (Random Access Machine), Definition 2.52 (LOOP construct), Definition 2.53 (Semantics of LOOP programs), Definition 2.54 (LOOP computable), Definition 2.55 (WHILE construct), Definition 2.56 (Semantics of the WHILE statement), Definition 2.57 (WHILE computable), Definition 2.58 (GOTO construct), Theorem 2.59 (LOOP vs WHILE programs), Theorem 2.60 (WHILE=GOTO), Corollary 2.61 (WHILEtotal=GOTOtotal), Definition 2.62 (WHILEif programs), Lemma 2.63 (WHILE=WHILEif), Theorem 2.64 (One WHILE loop suffices). 2.6 Hilberts 10. Problem: Definition 2.65 (Diophantine Equation), Definition 2.66 (Diophantine Set), Lemma 2.67 (Reduction), Lemma 2.68 (Reduction to diophantine eq. with exp), Theorem 2.69 (Matiyasevich (1970))
23.May.201101:33:45103
##### (Un-) Decidability
2. (Un-) Decidability: 2.6 Hilberts 10. Problem: Lemma 2.67 (Reduction), Lemma 2.68 (Reduction to diophantine eq. with exp), Theorem 2.69 (Matiyasevich (1970)), Corollary 2.70 (Hilberts 10th Problem is Undecidable). 2.7 Theorem of Rice: Definition 2.71 (Gödelization, Index), Theorem 2.72 (smn Theorem), Definition 2.73 (Index), Theorem 2.74 (Rice), Lemma 2.75, Theorem 2.78 (Recursion Theorem). 2.8 Oracle TMn: Definition 2.79 (Oracle TM MA), Definition 2.80 (Recursive, re in A), Definition 2.81 (Equivalence wrt. Turing Reducibility) and Definition 2.82 (Hierarchy), Theorem 2.83. 2.9 Reductions: Definition 2.84 (Reductions), Lemma 2.88, Definition 2.89.
30.May.201101:31:42134
##### SPACE versus TIME
3. SPACE versus TIME: 3.1 Basics: Definition 3.1 (NTIME(T(n)), DTIME(T(n))), Definition 3.2 (NSPACE(S(n)), DSPACE(S(n))), Theorem 3.3 (Tapes, Alphabet, States), Theorem 3.4 (Tape Compression), Corollary 3.5 (Tape Compression), Theorem 3.6 (Time Speed Up), Corollary 3.7 (Time Speed Up), Theorem 3.8 (Tape Reduction for TIME), Theorem 3.9 (Tape Reduction for SPACE), Lemma 3.10 (NTIME vs. DTIME). 3.2 Some Hierarchies: Theorem 3.11 (DSPACE(f(n)) Rec), Definition 3.12/13 ((Fully) Space/Time Constructible), Lemma 3.14, Definition 3.15 (Well-behaved Functions) and Lemma 3.16, Theorem 3.17 (Time/Space Hierarchies), Theorem 3.18 (Nondeterministic Hierarchies), Theorem 3.19 (Deterministic Hierarchies). 3.3 Relating TIME and SPACE: Theorem 3.20 (Relationship between TIME and SPACE), Theorem 3.21 (NSPACE vs. DSPACE (Savitch))
06.Jun.201152:1063
##### SPACE versus TIME
3. SPACE versus TIME: 3.3 Relating TIME and SPACE: Theorem 3.20 (Relationship between TIME and SPACE), Theorem 3.21 (NSPACE vs. DSPACE (Savitch)), Theorem 3.22, Lemma 3.23, Theorem 3.24 (Linear det. - linear nondet.). 3.4 More Properties: Theorem 3.25 (Union Theorem for SPACE), Theorem 3.26 (Union Theorem for TIME), Theorem 3.27 (Borodins Gap Theorem), Corollary 3.28 (Unintuitive Consequences), Theorem 3.29 (Blums Speed-Up Theorem).
06.Jun.201142:0663
##### SPACE versus TIME
3. SPACE versus TIME: 3.3 Relating TIME and SPACE: Theorem 3.20 (Relationship between TIME and SPACE), Theorem 3.21 (NSPACE vs. DSPACE (Savitch)), Theorem 3.22, Lemma 3.23, Theorem 3.24 (Linear det. - linear nondet.). 3.4 More Properties: Theorem 3.25 (Union Theorem for SPACE), Theorem 3.26 (Union Theorem for TIME), Theorem 3.27 (Borodins Gap Theorem), Corollary 3.28 (Unintuitive Consequences), Theorem 3.29 (Blums Speed-Up Theorem).
27.Jun.201101:34:4268
##### EXPSPACE
4. EXPSPACE: Theorem 3.17 (Time/Space Hierarchies). 4.1 Complexity classes: Definition 4.1 (From L to NEXPSPACE), Definition 4.2 (co-C), Lemma 4.3 (NSPACE(n)=Type-1), Theorem 4.4 (Immermann/Szelepcsenyi), Corollary 4.5 (CSL is closed under complements), Corollary 4.6 (Tight Space Hierarchy for NSPACE(S(n))), Lemma 4.7 (Number of Reachable Nodes), Lemma 4.8 (Rejecting NTM). 4.2 Reductions: Definition 4.9 (P-Time-,log-Space Reducibility), Lemma 4.10 (P-Time-and log Space Reductions), Definition 4.11 (Complete, Hard). 4.3 Structure of NP: Definition 4.12 (Psearch, NPsearch), Theorem 4.13, Definition 4.14 (Reachability: STCON, USTCON), Theorem 4.15 (Completeness of STCON and USTCON), Definition 4.16 (Boolean Expressions)
04.Jul.201101:23:3459
##### EXPSPACE
4. EXPSPACE: 4.3 Structure of NP: Definition 4.12 (Psearch, NPsearch), Theorem 4.13Definition 4.14 (Reachability: STCON, USTCON), Theorem 4.15 (Completeness of STCON and USTCON), Definition 4.16 (Boolean Expressions), Definition 4.17 (Satisfiability: SAT), Definition 4.18 (SAT, k-CNF, k-DNF), Definition 4.19 (Satisfiability: k-SAT), Lemma 4.20 (DNF and 2-SAT), Theorem 4.21 (Characterization of NP), Theorem 4.22 (SAT is NP-complete), Example 4.23 (More NP-Complete Problems), Lemma 4.24, Lemma 4.25, Lemma 4.26. 4.4 Oracles for P, NP: Definition 4.27 (PA, NPA)
11.Jul.201101:36:24108
##### EXPSPACE
4.4 Oracles for P, NP: Definition 4.27 (PA, NPA), Theorem 4.28 (Baker/Gill/Solovay). 4.5 PH - Polynomial Hierarchy: Definition 4.29 (LQBF), Definition 4.30 (Satisfiability: TQBF), Theorem 4.31 (LTQBF is PSPACE-complete), Definition 4.32 (Satisfiability: QSAT), Definition 4.33 (Alternating Turing Machine (ATM)), Definition 4.34 (Polynomial Hierarchy, ATM version), Lemma 4.35 (Relation between NTMs and ATMs), Lemma 4.36 (Relation: APTIME(f(n)), DSPACE(f(n))), Corollary 4.37 (PSPACE = APTIME), Corollary 4.38 (Relation between ATMs and TQBF), Definition 4.39 (MinDNF), Lemma 4.40, Definition 4.41 (Polynomial Hierarchy, Oracle version), Theorem 4.42 (ATMs and oracle TMs correspond), Corollary 4.43, Lemma 4.44. 4.6 Structure of PSPACE: Definition 4.45 (LCSG), Lemma 4.46 (CSG PSPACE), Definition 4.47 (Generalized L Tic-Tac-Toe), Theorem 4.48 (PSPACE completeness), Lemma 4.49 (Quasi-fixed rectangle). 4.7 EXPTIME/EXPSPACE: Lemma 4.50 (DTM accepting in k steps LDTM accept), Lemma 4.51 (n x n Checkers), Definition 4.52 (Regular expressions Lregex), Lemma 4.53 (Square Domino), Definition 4.54 (First order logic LFO), Definition 4.55 (Presburger/Peano Arithmetic), Definition 4.56 (R with addition/multiplication), Definition 4.57 (Quantifier Elimination), Lemma 4.58 (Quantifier Elimination (QE)), Lemma 4.59 (Reals with addition), Corollary 4.60 (Q and R are indistinguishable in L), Corollary 4.61 (Axioms for R, Q in L), Lemma 4.62 (Reals with addition and multiplication), Corollary 4.63 (Axioms for R in L), Lemma 4.64 (Presburger arithmetic), Corollary 4.65 (Axioms for N in L), Theorem 4.66 (Complexity of Arithmetic and R)
• ##### Short information

Semester: SS 2011

Lecture number: S 1228

English
20:00:03
31.Mar.2011
2.682
• ##### Contributors
Camera
Anja Michaela Kaiser
Lecturer
Prof. Dr. rer. nat. Jürgen Dix
• ##### Hints

Videoserver FAQ (in german only)