Theory of Computation (CS3102) Lecture 22 📚

This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html

Specific topics covered in this lecture:NP-completeness, tractability / parallelism, polynomial-time reducibilities, NP-hardness, Satiafiability, Cook-Levin theorem, "guess and verify" non-deterministic algorithms, why P=NP is difficult to resolve, robustness of P and NP, quantum computing, reduction types, 3-SAT, graph cliques, set covers, Hamiltonian cycles, graph coloring, partitioning