CSCI 0401

Computational Complexity

Computational Complexity
We will investigate the computational power of various resources. Examples include determining whether a computer with limited time or limited space can solve more difficult problems, attempting to characterize creativity as a resource, and comparing probabilistic and quantum computation. We will learn why we do not yet have answers to many of the most fundamental questions in computational complexity (like whether P=NP), and we will think critically about the value of studying these topics. 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), the review paper (non-expert computer science audience), and the popular science article (educated public audience). (CSCI 0301).3 hrs. sem./1 hr. disc.
Computer Science
Computer Science
Natural Sciences
Requirements Fulfilled:


Spring 2022

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

Fall 2020

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