computation model: RAM model versus a real processor, RAM model language versus high level languages,
Turing machine, one-tape-versus multi-tape TM, universal Turing machine, nondeterministic TM
computability: decidable languages, recursively enumerable sets, equivalent definitions of recursively enumerable sets,
undecidable problem, halting problem
other models of computations: PCP, lambda calculus, GOTO machines, equivalence of the computing models
complexity classes: time complexity, NP, NPC,
NP completeness of satisfiability: CIRCUIT SAT, SAT, NAESAT, 3SAT,
NP completeness of graph problems: Independent Set, Node Cover, Clique, MINCUT versus MAXCUT, MAX BISECTION,
HAMILTONIAN PATH, TRIPARTITE MATCHING