Simon Fraser University
Engaging the World

Course Outlines

Fall 2025 - CMPT 308 D100

Computability and Complexity (3)

Class Number: 5484

Delivery Method: In Person

Overview

  • Course Times + Location:

    Sep 3 – Dec 2, 2025: Wed, 9:30 a.m.–12:20 p.m.
    Burnaby

  • Exam Times + Location:

    Dec 13, 2025
    Sat, 3:30–6:30 p.m.
    Burnaby

  • Prerequisites:

    (MACM 201 or CMPT 210) with a minimum grade of C-.

Description

CALENDAR DESCRIPTION:

Formal models of computation such as automata and Turing machines. Decidability and undecidability. Recursion Theorem. Connections between computability and logic (Gödel’s Incompleteness). Time and space complexity classes. NP-completeness.

COURSE DETAILS:

This course focuses on the inherent "complexity" of solving problems using a computer. The goal is to understand why some seemingly simple problems cannot be solved on computers and others have no efficient (ie fast) solution. In the course, we will see the formal notions of computers, computability and complexity. At the successful completion of this course students will understand why, for example, computer viruses are so pervasive and why no one will ever write a perfect virus checker. We will see how these concepts are related to logic, in particular, the famous Incompleteness Theorem of Godel. Finally, we will see a few surprising results from modern complexity, in particular, the results making use of randomness in computation.

Topics

  • Turing Machines as a formalization of the intuitive notion of an algorithm.
  • Computability (Does a program exist?): basic computability (checking if a program is in an infinite loop), reducibilities and oracles, the Recursion Theorem (existence of computer viruses).
  • Review of Logic and Godel's Incompleteness Theorem.
  • Complexity Theory: Non-determinism, the class NP, reductions.
  • Randomness in Computation: Interactive Proofs.
  • Approximation algorithms and hardness of approximation: Probabilistically Checkable Proofs and the PCP Theorem.

Grading

NOTES:

There will be 4 ungraded assignments, 4 in-class 50-min quizzes (15% each), and a final examination (40%). 

Students must attain an overall passing grade on the weighted average of exams in the course in order to obtain a clear pass (C- or better).

Materials

MATERIALS + SUPPLIES:

Reference Books

  • Introduction to Automata Theory, Languages and Computation - 3rd Edition, J.E. Hopcroft , Rajeev Motwani, J.D. Ullman, , Addison Wesley, 2006, 9780321455369

REQUIRED READING:

Introduction to the Theory of Computation 3rd Edition
Michael Sipser,
Cengage Learning,
2012
ISBN: 9781133187790

REQUIRED READING NOTES:

Your personalized Course Material list, including digital and physical textbooks, are available through the SFU Bookstore website by simply entering your Computing ID at: shop.sfu.ca/course-materials/my-personalized-course-materials.

Department Undergraduate Notes:

The following are default policies in the School of Computing Science. Please check your course syllabus whether the instructor has chosen a different policy for your class, otherwise the following policies apply.
 
  • Students must attain an overall passing grade on the weighted average of exams in the course in order to get a C- or higher.
  • All student requests for accommodations for their religious practices must be made in writing by the end of the first week of classes, or no later than one week after a student adds a course. After considering a request, an instructor may provide a concession or may decline to do so. Students requiring accommodations as a result of a disability can contact the Centre for Accessible Learning (caladmin@sfu.ca).

Registrar Notes:

ACADEMIC INTEGRITY: YOUR WORK, YOUR SUCCESS

At SFU, you are expected to act honestly and responsibly in all your academic work. Cheating, plagiarism, or any other form of academic dishonesty harms your own learning, undermines the efforts of your classmates who pursue their studies honestly, and goes against the core values of the university.

To learn more about the academic disciplinary process and relevant academic supports, visit: 


RELIGIOUS ACCOMMODATION

Students with a faith background who may need accommodations during the term are encouraged to assess their needs as soon as possible and review the Multifaith religious accommodations website. The page outlines ways they begin working toward an accommodation and ensure solutions can be reached in a timely fashion.