When does a problem have an effective algorithmic solution? What does it mean for an algorithm to be effective? In this subject we attempt to give rigorous meaning to questions of this type and investigate some possible answers. Abstract computing machines and their role in the definitions of various notions of computational complexity will be discussed. Classes of problems such as P, NP will be defined and a number of well known problems in graph theory, algebra and applied discrete mathematics will be classified according to their computational complexity. The second half of the subject covers undecidability for decision problems: problems for which no algorithmic solution is possible. This property is found amongst problems from computing, abstract algebra, combinatorics, matrices and the theory of tilings.

Subject rules