Large-scale Knowledge Processing: Lecture 8
2025.12.25 (Thu) 2nd period
Today's Lecture:Foundations on Theory of Computation (2)
- Reduction
- NP-complete Problem
- Polynomial-time Reduction from CNF-SAT to 3SAT
- Polynomial-time Reduction from 3SAT to Vertex Cover Problem
Materials
Slides
2025.12.24 Constructed. Lecturer:Kazuhisa Seto
seto @ ist.hokudai.ac.jp