Abdul Hadi Asfarangga, The University of Adelaide
Associate Professor Youming Qiao, University of Technology Sydney
Computational complexity studies algorithmic problems in terms of the resources, such as time and memory, required to solve them. Since the introduction of the famous P vs NP problem in the 1970s, this theory has evolved into a major new mathematical program in the 21st century, providing insights into practical computational paradigms and tasks such as randomised algorithms, approximation algorithms, average-case algorithms, cryptography, and quantum algorithms.
This course is an introduction to computational complexity, with a focus on those mathematical theories developed to understand the computational paradigms and tasks described above. Efforts will be made to highlight connections to other branches of mathematics such as combinatorics and algebra.
Topics covered in this course include:
There is no set text book for this course, and full lecture notes will be provided. However similar material to that covered can be found in:
Take this quiz and look at some of the expected foundational skills in this topic