Computability: Turing Machines (T. M. with multiple tapes, Non-deterministic T. M.), Church – Turing Thesis
Time Complexity: Complexity relations between different T. M. models (single-tape, multiple tapes, non- deterministic), Time complexity of non-deterministic T. M., The complexity classes P, NP, coNP, EXP, Reductions and completeness, the notion of NP-hardness, Cook-Levin Theorem, NP-complete languages, Pseudopolynomial and strongly NP-complete languages
Space Complexity: Savitch’s Theorem, The complexity class PSPACE and PSPACE-completeness, The complexity classes L, NL, EXPSPACE, NL-completeness
Hierarchy Theorems: The Time Hierarchy Theorem, The Space Hierarchy Theorem
INSTRUCTOR
COURSE DESCRIPTION: