0368.3168 --- Complexity

The Turing machine and RAM models of computation;
time and space complexity;
the classes P, NP, co-NP, NPC, PSPACE, EXP, L, NL;
polynomial reductions; Cooks's theorem; NP-hardness;
other complexity classes; hierarchy theorems;
psedu polynomial algorithms; approximation algorithms.

Textbook: Christos H. Papadimitriou; Computational complexity