David Witmer

Professor

Carnegie Mellon University

1 course · 1 total lecture · 1h recorded

Algorithms & Theoretical CS

Courses by David Witmer

All courses →

Complete university lecture series taught by David Witmer.

CMU 15-455: Undergraduate Complexity Theory

Carnegie Mellon University · 15-45520 lectures · 27h

Theory & Algos·undergraduate

Undergraduate Complexity Theory

Prof. Ryan O'Donnell·Carnegie Mellon University

Rigorous introduction to computability and complexity theory, covering Turing machines, diagonalization, NP-completeness, space complexity, Savitch's theorem, and the polynomial hierarchy.

Start lecture 1

Syllabus →

All lectures by David Witmer

Search or browse every recorded session across courses and talks.

Showing 1 of 1 lectures

Lecturej/k navigate · c chapters · s save · x watched

Scholar · University

Chapters · Duration

Lecture 12: NP-Completeness Reductions (15-455)

15-455 · Lec 12 · David Witmer · Carnegie Mellon University

David Witmer Carnegie Mellon University

1:20:32