CSCI 0401

Computational Complexity

Computational Complexity
We will study models of computation and investigate whether a model of computation can solve a given problem efficiently or not. We will consider models that involve all-knowing provers, constrained space, communication limitations, randomness, and quantum resources, among others. While not all of these models are realistic, by studying them, we will gain insight into why certain classes of problems are easy or difficult to solve. Students enrolled in the College Writing (CW) section of the course will explore these ideas through writing, in particular, in three contexts that are critical for theoretical computer science: the proof (expert audience), a review paper (non-expert computer science audience), and a popular science article (educated public audience). (CSCI 0301 and CSCI 0302, or instructor approval).3 hrs. sem./1 hr. disc.
Computer Science
Computer Science
Natural Sciences
Requirements Fulfilled:


Spring 2022

CSCI0401A-S22 Seminar (Kimmel)
CSCI0401Z-S22 Lab (Kimmel)

Fall 2020

CSCI0401A-F20 Seminar (Kimmel)
CSCI0401B-F20 Seminar (Kimmel)