linden.study

MATH 4316 Computability and Computational Complexity

This is a course in the theoretical foundations of computer science, centered around the theme of fundamental limits on computation. Topics include: Turing Machines, universal computation, undecidability of the halting problem, solvable and unsolvable algorithmic problems, recursive functions, Goedel's Incompleteness Theorem, time- and space-bounded computations, Cook's Theorem, NP-complete problems, problems solvable in polynomial space, randomized computation, application to cryptography, practical approaches to computationally intractable problems (such as SAT solvers), quantum computing, and Shor's Theorem.

Course overview

Department
Mathematics
School
MCAS
Credits
3
Level
Undergraduate
Offered
Every Fall,Periodically in the Spring

Catalog details

Prerequisites
CSCI2243 or MATH2216
Corequisites
CSCI2244 or MATH4426

Catalog text is imported from the reviewed Boston College course snapshot. Confirm eligibility in EagleApps.

Requirements fulfilled

  • Mathematics B.A.: 4000-level Mathematics elective options (Current University Catalog; students should confirm their catalog year)
  • Mathematics B.S.: 4000-level Mathematics elective options (Current University Catalog; students should confirm their catalog year)
  • Computer Science B.S.: Upper-level mathematics option (Current University Catalog; students should confirm their catalog year)

Requirement eligibility can vary by school, cohort, and section. Confirm the selected section in EagleApps or with an advisor.

Official evaluation summary

No source-backed aggregate rating is available yet.

Data freshness

Course and evaluation data last updated 2026-08-02. Source details and limitations are documented in Data Sources and Methodology.

Instructors

Sections

  • Section 01
    Fall 2026 · Alexander Creiner · 245 Beacon Street Room 230 MW 03:00PM-04:15PM · Offered