Deterministic Complexity Classes - Lecture 23 📘

Introduction to Theoretical Computer Science. Lectures as given at Kutaisi International University (Kutaisi, Georgia), during spring semester 2025. Instructor: George Nadareishvili; slides: mostly by Wolfgang Paul. More information can be found at gnadareishvili.com

In this lecture, we start to discuss the theory of deterministic complexity classes. We define time and space bounded Turing machines and the corresponding classes of languages. We prove that accepting and deciding are equivalent for time and space bounded machines, as well as demonstrate tape reduction theorems.

Kutaisi International University: https://www.kiu.edu.ge/
More information about the course and the instructor: https://gnadareishvili.com/