Theory of Computation
https://uvatoc.github.io/week11
24.2 Introducing NP
- Is LongestPath in P?
- Is LongestPath in EXP?
- Making LongestPath a Decision Problem
- Find the Longest Path (song by Daniel J. Barrett)
- Introducing class NP
The "Find the Longest Path" song is from http://www.jakubw.pl/inne/longest.html (and video from https://www.youtube.com/watch?v=a3ww0gwEszo).
The people in the Longest Path song video (all of whom have made substantial contributions to theory of computation) are, in order of appearance: Shafi Goldwasser, Virginia Vassilevska Williams, Julia Chuzhoy, Sofya Raskhodnikova, and Barna Saha.
David Evans and Nathan Brunelle
University of Virginia
