Theory of Computation
uvatoc.github.io/week11
24.3 Complexity Class NP
- Informal Notion of Class NP
- Nondeterministic Machines
- "Power" of Machines
- (review) NFAs are equivalent in power to DFAs
- Are things different for TMs? (answered in next segment)
Nathan Brunelle and David Evans
University of Virginia
5 июл 2024
