Theory of Computation and Complexity
Course Description :

Finite Automata and Regular Languages, Properties of Finite Automata, Regular Expressions, The Pumping Lemma and Closure Properties; Universal Models of Computation, Encoding Instances, Choosing a Model of Computation, Model Independence, Turing Machines as Enumerators and Acceptors; Computability Theory, Primitive Recursive Functions, Partial Recursive Functions, Arithmetization: Encoding a Turing Machine, Programming Systems, Recursive and R.E. Sets, Rice's Theorem and the Recursion Theorem, Degrees of Unsolvability; Complexity Theory, Reductions, Classes of Complexity, Complete Problems; Some Important NP-Complete Problems, The Complexity of Approximation, Models of Parallel Computation, Communication and Complexity, Interactive Proofs and Probabilistic Proof Checking

Department :Computer Science
Program :MSc. of Computer Science
Course Level :Master
Course Outline :

King Abdullah II School of Information Technology
Department of Computer Science


  • Saying goodbye to my wonderful faculty is more nostalgic than simple words can describe; it has truly become a second home. ... Eman Ennab

  • King Abdullah II College for Information Technology was and still maintains the pertinent atmosphere for volunteering in many sci ... Yousef Arabiat

  • Despite having differences between the study experiences and real work experience, the university is the pillar for building care ... Abed Abuhijleh