Fundamentals of the theory of computation and complexity theory. Computability, undecidability, and logic. Relations between complexity classes, NPcompleteness, P-completeness, and randomized computation. Applications in selected areas such as cryptography, logic programming, theorem proving, approximation of optimization problems, or parallel computing.