FIT3236 · Monash University
Theory of computation 2: Complexity and intractability
- Credit points
- 6
- Level
- 3
- Workload
- —
- Faculty
- Information Technology
What it covers
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.
Assessment
Assessment not published yet.
When and where
Not offered in 2027, or offerings not published yet.