FIT3236 Theory of computation 2: Complexity and intractability

This unit studies the complexity of computation across several major kinds of computational tasks, including decision problems, function problems, enumeration problems, and counting problems. It develops a rigorous understanding of asymptotic analysis, polynomial-time reducibility, completeness, tractability, and intractability, and examines major complexity classes as well as the polynomial hierarchy. The unit also introduces randomised computation and quantum computation as alternative models of efficient computation, and explores how they reshape our understanding of what can be solved efficiently. You will learn how to classify problems, compare their computational difficulty, and use representative example problems and explicit reductions to study complexity from a practical perspective, so that theoretical results are connected directly to algorithm design and to recognising when efficient exact solutions are unlikely.