LEJ4Learning

1. Introduction to Theory of Computation an…
2. Set Thoery, Sets, Sequences, tuples, Fun…
3. Turing Machine and Its Language
4. Designing Turing Machines
5. Variants of Turing Machines
6. Enumerators, Dovetailing, The Church-Tur…
7. Decidable Languages, The Acceptance Prob…
8. The Halting Problem, Universal TM
9. Undicidability of the Halting Problem
10. Linear Bounded Automata, Computation His…
11. Russell’s Paradox, Reducibility, Emptine…
12. Post Correspondence Problem, Computable …
13. Computable Functions, Reducibility
14. Reducibility, Recursion Theorem
15. Recursion Theorems, Logical Theories
16. Logical Theories
17. Logical Theories, Godel’s Theorem
18. Oracles, Turing Reducibility
19. A definition of information, Incompressi…
20. Incompressible Strings, Complexity Theor…
21. Big Oh, Little Oh Notations, Time Comple…
22. Non-Deterministic Time, The Class P, The…
23. The Class NP, Polynomial Time Verifiers
24. The Class NP
25. Subset Sum Problem, Satisfiability
26. NP-Completness, Satisfiability, 3-Color
27. Satisfiability
28. The Cook-Levin Theorem
29. NP-Completeness, Independent Sets
30. Independent Sets, NP-Completeness, Cliqu…
31. NP-Completeness, Clique, Vertex Cover
32. Hamiltonian Path Problem
33. The Subset Sum Problem
34. The Traveling Salesman Problem
35. An Approximation Algorithm for TSP Probl…
36. Space Complexity
37. Space Complexity (Cont.)
38. Relationship between Space and Time Comp…
39. TQBF, Prove that TQBF is PSPACE-Complete
40. TQBF, FORMULA-GAME, Generalized Geograph…
41. Generalized Geography (Cont.)
42. LOGSPACE Transducer
43. Prove the Theorem: NL = co-NL
44. Prove the Theorem: NL = co-NL (Cont.)
45. Overview of the course covered

Meta Search Engine