FIT3236 · Theory of computation 2: Complexity and intractability

Overview

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.

Offerings

The Handbook publishes no offerings for this unit.

Assessment

The Handbook publishes no assessment items for this unit yet.

Assessment details may change. Please refer to the assessment information in Moodle closer to the start of the teaching period.

Requisites

Learning outcomes

1. Investigate the complexity of computational problems by constructing explicit reductions, classifying problems within complexity classes and evaluating the implications for tractability;
2. Design, code, test and document programs that implement representative algorithms across complexity classes, including randomised and approximation strategies for hard problems;
3. Examine mathematical models of real-world computational problems through reductions, separations and analyses across classical, randomised and quantum computation.

Workload

No workload detail published.

Student experience, not official rules. Nothing here changes what the Handbook says.