Video-Server > Vorlesungen > Komplexitätstheorie

# Komplexitätstheorie

by Prof. Dr. rer. nat. Jürgen Dix 19:58 hrs2.338 Views31.Mar.2011
 Camera Anja Michaela Kaiser

## Information about the videoserver and -player

You can find information about the videoserver and the player in the videoserver FAQ (in german only).

### The Chomsky Hierarchy

01:20 hrs04.Apr.2011906 Views

Topics:
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)).

### The Chomsky Hierarchy

01:35 hrs06.Apr.2011206 Views

Topics:
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)

### The Chomsky Hierarchy

01:09 hrs11.Apr.2011129 Views

Topics:
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

### The Chomsky Hierarchy

19:45 min11.Apr.2011122 Views

Topics:
1. The Chomsky Hierarchy: 1.6 Ehrenfeucht: 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).

### (Un-) Decidability

34:37 min18.Apr.2011121 Views

Topics:
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)

### (Un-) Decidability

28:44 min18.Apr.201187 Views

Topics:
2. (Un-) Decidability: 2.2 PCP: Theorem 2.10 (Undecidability of PCP), Lemma 2.11, 2.12, 2.13

### The Chomsky Hierarchy and (Un-) Decidability

26:49 min18.Apr.201180 Views

Topics:
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)

### (Un-) Decidability

01:39 hrs02.May.201186 Views

Topics:
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)

### (Un-) Decidability

01:38 hrs09.May.201179 Views

Topics:
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)

### (Un-) Decidability

01:31 hrs16.May.201166 Views

Topics:
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))

### (Un-) Decidability

01:33 hrs23.May.201171 Views

Topics:
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.

### SPACE versus TIME

01:31 hrs30.May.2011102 Views

Topics:
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))

### SPACE versus TIME

52:09 min06.Jun.201152 Views

Topics:
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).

### SPACE versus TIME

42:06 min06.Jun.201150 Views

Topics:
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).

### EXPSPACE

01:34 hrs27.Jun.201154 Views

Topics:
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)

### EXPSPACE

01:23 hrs04.Jul.201140 Views

Topics:
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)

### EXPSPACE

01:36 hrs11.Jul.201187 Views

Topics:
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)

Impressum · Kontakt · Datenschutz© TU Clausthal 2019