##
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

### Literature

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).