CS 675 - Computability and Complexity

Bulletin Description

The formal study of computation, including computability and computation with limited resources. Church's thesis and models of computation. Topics will include Turing machines or other basic models of computation; reductions; computable and computably enumerable sets; Rice's Theorem; decidability and undecidability; basic complexity theory; NP-completeness and notions of intractability. Additional topics may include primitive recursive functions and the Grzegorczyk hierarchy; nondeterminism; the arithmetic hierarchy; formal complexity measures; time and space hierarchy theorems; the polynomial hierarchy and PSPACE; probabilistic complexity classes; circuit complexity.


CS 575 or consent of instructor.

Expected Preparation

Students should be familiar with elementary logic and comfortable doing formal proofs. They should have been exposed to some formal models of computation prior to this class.

Student Learning Outcomes


Successful students will learn:

· Basic models of computation, and relationships among them

· Notions of decidability and proofs of undecidability

· Foundations for complexity analysis of algorithms

· Notions of time and space complexity and their tradeoffs

· The power of nondeterminism in computation with and without resource bounds

The week-by-week outline will depend on the emphasis of the course (on computability or on complexity), at the discretion of the instructor.


Syllabus Information

Graded work:

Exact details about graded work in this course will be determined by the instructor offering the course and will be made available in the syllabus during the first class meeting. Typically there will be an in-class presentation by the student, bi-weekly homework, and a two-hour final examination.


A student's grade will be determined by a weighted average of homework assignments, midterm, and the final examination. The faculty offering the course will make the details available at the start of the course. A typical weighting is:

Homework: 40%
Presentation: 25%
Final Examination: 35%

Possible Textbooks:

Garey and Johnson,
Computers and Intractability,
Freeman, 1997

Computational Complexity
Addison Wesley 1996