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.
Master of Computing in Information Systems
Data will be available soon!
| content serial | Description |
|---|
Start your application
