Complexity theory
| Course Code: | Ε10 |
| Course Level: | Undergratuate |
| Obligatory/Elective: | Elective |
| Semester: | 9 |
| Division: | Division of Computers |
| Group: | Group A |
| ECTS Credits: | 5 |
| Hours Per Week: | 4 |
| Website: | eclass.uowm.gr/courses/ICTE266/ |
| Language: | Greek |
| Content: | Problems, algorithms and computational complexity. Turing machines, Non-deterministic Turing machines. Global Turing machines. The position of Church. Recursive functions, computability and incomputability, time and space bounded computation, retrospective and back countable languages, deterministic and non-deterministic time classes and space classes, LOGSPACE, NL, P, NP, PSPACE, etc; Cook-Levin theorem |
| Learning Outcomes: |
|
| Pre-requirements: | - |
| Teaching Methods: | Lectures, Notes, Exercises |
| Validation: | Assignment (30% of the total mark) and exams (70% of the total mark) |
| Suggested Books: |
|