Uploaded April 2018 | Updated September 2026, 17 minutes ago
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
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
