In the Winter term, we will discuss computability in the broader
setting of mathematics. Some of the highlights here are a development
of the Godel Incompleteness Theorems, the Boone-Novikov theorem on the
undecidability of the word problem for groups, and the basics of the
theory of algorithmic randomness. We will also discuss many examples
of undecidable problems from logic, number theory, group theory,
combinatorics, and computer science. No prior knowledge of any of
these subjects is assumed. We will develop all the necessary
background.
In the Spring term, we will start with a discussion of decidable
problems, i.e., problems for which there are actually algorithms for
their solution. Then we will introduce the basic concepts of the
theory of computational complexity of algorithms. We will study the
concept of feasible (polynomial time) computation and the relationship
between deterministic polynomial (P) and nondeterministic polynomial
(NP) computations, including NP-complete problems and the famous "P =
NP" problem. We will also discuss probabilistic algorithms and
derandomization.
|
