Lesson 49 — Bài toán khó & P vs NP
Ba module tương tác: bản đồ các lớp P / NP / NP-complete / NP-hard, Verify vs Solve trên subset sum, và 2-approximation vertex cover so với tối ưu.
Module 1 — Bản đồ các lớp độ phức tạp
Click một bài toán bên dưới để xem nó nằm ở vùng nào trong sơ đồ Venn. Giả thiết P ≠ NP (nên P là vùng con thật sự của NP).
P — giải nhanh
NP — verify nhanh
NP-hard — khó nhất trở lên
Click một bài toán để xem phân loại.
Module 2 — Verify vs Solve (Subset Sum)
Bài: tập có tập con tổng đúng không?
Solve thử mọi tập con (2ⁿ, chậm). Verify nhận sẵn 1 tập con, chỉ cộng lại (nhanh).
🐢 Solve — thử mọi tập con
Duyệt 2ⁿ tập con cho tới khi tìm thấy tổng = T.
Đã thử: 0 / 0 tập
⚡ Verify — nhận sẵn lời giải
Certificate cho sẵn — chỉ cộng & so với T.
Phép cộng: 0
Đặt bài rồi so sánh: solve chậm (2ⁿ) vs verify nhanh (n).
Module 3 — Approximation: Vertex Cover 2-approx vs Optimal
Đồ thị nhỏ. 2-approx ghép cặp cạnh chưa phủ, thêm CẢ 2 đỉnh.
Optimal tìm cover nhỏ nhất bằng brute-force. So ratio = |approx| / OPT (luôn ≤ 2).
Chọn đồ thị rồi chạy. Đỉnh tô màu = thuộc cover.