CS 590 - Computational Complexity

Institution:

DigiPen Institute of Technology

Subject:

Description:

Prerequisite(s): CS 280, CS 330, or Equivalent The study of computational complexity is at the core of theoretical computer science. The key issue to understand in complexity theory is the nature of efficient computation. Hence, it is a natural extension of computability theory, which studies the nature of computation without regard for resource bounds. This course addresses questions such as: What is an algorithm? What problems can or cannot be solved by an algorithm? What problems can or cannot be solved efficiently by an algorithm? How can we classify and compare problems according to their intrinsic computational complexity? Exploring this last question will constitute the bulk of the course. Students will be introduced to ways to compare computational problems, even when we do not know how to solve them efficiently. They will also study the complexity classes (e.g. P, NP, PSPACE, L, NL, BPP, etc.) into which they fall. As the course progresses, students will be led to examine more questions, such as: Is it easier (more efficient) to comply seek approximate solutions? Can flipping coins help in designing efficient algorithms? Can biology and/or physics lend a hand?

Credits:

3.00

Credit Hours:

Prerequisites:

Corequisites:

Exclusions:

Level:

Instructional Type:

Lecture

Notes:

Additional Information:

Historical Version(s):

Institution Website:

www.digipen.edu

Phone Number:

(425) 558-0299

Calendar System:

Semester

The Course Profile information is provided and updated by third parties including the respective institutions. While the institutions are able to update their information at any time, the information is not independently validated, and no party associated with this website can accept responsibility for its accuracy.