Computational Complexity

CS254

Stanford School of Engineering


Stanford campus image

Description

An introduction to computational complexity theory. Topics include the P versus NP problem and other major challenges of complexity theory; Space complexity: Savitch's theorem and the Immerman-Szelepscényi theorem; P, NP, coNP, and the polynomial hierarchy; The power of randomness in computation; Non-uniform computation and circuit complexity; Interactive proofs.

Prerequisites

CS154 or equivalent; mathematical maturity.

Notes

Note on Course Availability

The course schedule is displayed for planning purposes – courses can be modified, changed, or cancelled. Course availability will be considered finalized on the first day of open enrollment. For quarterly enrollment dates, please refer to our graduate education section.

002 Winter 2020-21 Online
Dates:January 11 - March 19, 2021
Units: 3.00
Instructors: Li-Yang Tan
Delivery Option:
Online
Fees:
For Credit $4,056.00
Notes: Pre-registration Dates: November 2, 2020 at 9:00am to December 4, 2020 at 5:00pm

Computer Science Department Requirement
Students taking graduate courses in Computer Science must enroll for the maximum number of units and maintain a B or better in each course in order to continue taking courses under the Non Degree Option.

Pre-registration for this course will secure your enrollment request and ensure timely processing of your application for potential course approval. Please note: course enrollment will be confirmed after December 11, 2020; after completing your pre-registration, no further action is required on your part.

 

This course may not currently be available to learners in some states and territories.