Theory of Computability and Complexity

Description

This course covers the theoretical computer science areas of computability and complexity. The course starts by introducing the formal languages and their related theories. Then, it covers topics in computability which includes Turing machines and their variants, halting problem, decidable and undecidable problems, and reducibility. Complexity Theory covers the topics of time and space measures, complexity classes P, NP, L, NL, PSPACE, BPP and IP, complete problems, P versus NP conjecture, quantifiers and games, provably hard problems, relativized computation and oracles, probabilistic computation, and interactive proof systems.

Program

Master of Computing in Computer Science

Objectives

• Data will be available soon!