Not currently offered

Credit points: 15

Subject outline

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.

SchoolEngineering and Mathematical Sciences

Credit points15

Subject Co-ordinatorMarcel Jackson

Available to Study Abroad/Exchange StudentsYes

Subject year levelYear Level 4 - UG/Hons/1st Yr PG

Available as ElectiveNo

Learning ActivitiesN/A

Capstone subjectNo

Subject particulars

Subject rules

Prerequisites Students must have completed MAT1DM and MAT2AAL and MAT1CLA or any Level three Mathematics subject.


Incompatible subjectsN/A

Equivalent subjectsN/A

Quota Management StrategyN/A

Quota-conditions or rulesN/A

Special conditionsOffered subject to sufficient enrolments.

Minimum credit point requirementN/A

Assumed knowledgeN/A

Career Ready


Work-based learningNo

Self sourced or Uni sourcedN/A

Entire subject or partial subjectN/A

Total hours/days requiredN/A

Location of WBL activity (region)N/A

WBL addtional requirementsN/A

Graduate capabilities & intended learning outcomes

Graduate Capabilities

Intended Learning Outcomes

01. Demonstrate advanced theoretical and technical knowledge in computational complexity
02. Use advanced cognitive and technical skills to select and apply methods to critically analyse, evaluate and interpret tasks relevant to computational complexity
03. Use advanced cognitive and technical skills to analyse, generate and transmit solutions to complex problems relevant to computational complexity.
04. Use advanced communication skills to transmit complexity-theoretic knowledge and ideas to others.
05. Demonstrate autonomy, well-developed judgement, adaptability and responsibility as a mathematician.

Subject options

Select to view your study options…

Start date between: and    Key dates

Subject not currently offered - Subject options not available.