Video-Server > Vorlesungen > Komplexitätstheorie

Komplexitätstheorie

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

19:58 hrs2.287 Views31.Mar.2011
Camera Anja Michaela Kaiser

Information about the player

Please activate javascript in order to play the recordings on this website. For all Browsers the current version of the Adobe Flash Player is needed.



Lectures


The Chomsky Hierarchy

Lecture no. 1

01:20 hrs04.Apr.2011869 Views

Start lecture

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

Lecture no. 2

01:35 hrs06.Apr.2011201 Views

Start lecture

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

Lecture no. 3

01:09 hrs11.Apr.2011129 Views

Start lecture

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

Lecture no. 4

19:45 min11.Apr.2011122 Views

Start lecture

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

Lecture no. 5

34:37 min18.Apr.2011120 Views

Start lecture

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

Lecture no. 6

28:44 min18.Apr.201187 Views

Start lecture

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

Lecture no. 7

26:49 min18.Apr.201180 Views

Start lecture

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

Lecture no. 8

01:39 hrs02.May.201183 Views

Start lecture

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

Lecture no. 9

01:38 hrs09.May.201179 Views

Start lecture

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

Lecture no. 10

01:31 hrs16.May.201166 Views

Start lecture

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

Lecture no. 11

01:33 hrs23.May.201171 Views

Start lecture

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

Lecture no. 12

01:31 hrs30.May.2011100 Views

Start lecture

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

Lecture no. 13

52:09 min06.Jun.201151 Views

Start lecture

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

Lecture no. 14

42:06 min06.Jun.201150 Views

Start lecture

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

Lecture no. 15

01:34 hrs27.Jun.201152 Views

Start lecture

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

Lecture no. 16

01:23 hrs04.Jul.201140 Views

Start lecture

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

Lecture no. 17

01:36 hrs11.Jul.201187 Views

Start lecture

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© TU Clausthal 2017