Large-scale Knowledge Processing: Lecture 8

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

• Slide (in Japanese)
• Slide (in English)

2025.12.24 Constructed. Lecturer：Kazuhisa Seto