+251 111 559769      info@hilcoe.net
     +251 111 559769      info@hilcoe.net

Complexity Theory  

Course Objectives

At the end of the course, students will

  • explain models of computation, resources (time and space), algorithms, computability, and complexity,
  • learn randomized computation and complexity; logical characterizations, incompleteness and approximability, and
  • understand circuit complexity, lower bounds; parallel computation and complexity; counting problems and interactive proofs.

Course Description

Turing machines: standard TM, computability of TM, techniques of TMs construction, Church’s hypothesis; computability (introduction to recursive function theory; primitive and partial recursive functions, recursive and recursively enumerable languages, Turing computable); undecidability (Turing decidable and Turing acceptable, undecidable problems); computational complexity (basics of algorithm analysis: Big O-notation, polynomial time and space; nondeterministic polynomial time; P vs NP, polynomial time reductions and NP-complete problems: Cook’s theorem).

Course Content

  1. Turing Machines (TMs)
  2. Computability
  3. Undecidability
  4. Computational Complexity