Complexity (סיבוכיות)

This course supplements the introductory course in the theory of computation, and expands on topics in Complexity Theory.

Topic summary:

Turing machines, simulations and the RAM
Time and space complexity classes
The Hierarchy Theorem
Polynomial-time reductions and Complete Problems
NP and NP-Completeness
Oracles and relativized classes


Introdution to the Theory of Computation by Sipser

Computers and Intractability by Garey and Johnson

Introduction to Automata Theory, Languages and Computation by Hopcroft, Motwani and Ullman (also earlier version by Hopcroft and Ullman).