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.
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).
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).
Thử: verify một tập con — cộng vài số là xong (đa thức); solve — phải mò trong 2ⁿ tập: khoảng cách verify/solve chính là P vs NP.
🐢 Solve — thử mọi tập con
Duyệt 2ⁿ tập con cho tới khi tìm thấy tổng = T.
⚡ Verify — nhận sẵn lời giải
Certificate cho sẵn — chỉ cộng & so với T.
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).