• Student home
• Things to know this week
• Student news
• Student events
• New students' welcome
• Studying at York
  • Semesters
  • Teaching hours
  • Enrolment
  • Manage your studies
    • Enrol or re-enrol
    • Your student record
    • Your timetable
    • Change your plan
    • Programmes and modules
      • Programme specifications
      • Studying beyond your department
      • Module catalogue
    • University study spaces
  • Student Visa holders
  • Study skills
  • Assessment and examination
  • Academic progress issues
  • Graduation
• Support and advice
• Health and wellbeing
• Work, volunteering and career planning
• Study and work abroad
• Accommodation
• IT and online services
• Finance
• Student life in York
• If things go wrong
• Student Centre

Theory 3: Computability & Complexity - COM00023I

« Back to module search

• Department: Computer Science
• Module co-ordinator: Dr. Detlef Plump
• Credit value: 10 credits
• Credit level: I
• Academic year of delivery: 2021-22
  • See module specification for other years: 2022-23

Module summary

Computability and Complexity

Related modules

Module will run

Occurrence	Teaching period
A	Autumn Term 2021-22

Module aims

The aim of this module is to introduce basic concepts and results in computability theory and complexity theory. In particular, students will learn the concepts of Turing-recognizable languages and Turing-computable functions, and the difference between solvable and unsolvable problems. They will be able to prove unsolvability by reduction. They will understand the time and space complexity of Turing machines, and complexity classes such as P, NP, PSpace, NPSpace and NPC. They will be able to prove NP-completeness by reduction.

Module learning outcomes

T301	Determine a language’s place in the Chomsky hierarchy (regular, context-free, context-sensitive or recursively enumerable).
T302	Provide examples of unsolvable problems.
T303	Prove that a problem is unsolvable by reducing a known unsolvable problem to it.
T304	Explain the Church-Turing thesis and its significance.
T305	Define the classes P and NP, and explain their relation to the class ExpTime.
T306	Explain the significance of NP-completeness and provide examples of NP-complete problems.

Assessment

Task	Length	% of module mark
Online Exam -less than 24hrs (Centrally scheduled) Theory 3	3 hours	100

Special assessment rules

None

Reassessment

Task	Length	% of module mark
Online Exam -less than 24hrs (Centrally scheduled) Theory 3	3 hours	100

Module feedback

Feedback is provided through work in practical sessions, revision classes, and after the final assessment as per normal University guidelines.

Indicative reading

**** Martin, John C., Introduction to Languages and the Theory of Computation (4th ed.), McGraw Hill, 2010

** Rich, Elaine, Automata, Computability and Complexity, Pearson Education, 2008

** Sipser, Michael, Introduction to the Theory of Computation (3rd ed.), South-Western College Publishing, 2012

* Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D., Introduction to Automata Theory, Languages and Computation (3rd ed.), Pearson Education, 2013

* Arora, Sanjeev and Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge University Press, 2009

++ Garey, Michael R. and Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979