Video
P và NP: kiểm một đáp án dễ — vậy tìm có dễ không?
Kiểm một đáp án thì dễ, vậy tìm ra đáp án có dễ không?
Hoạt động
Sinh viên cảm nhận được sự chênh lệch giữa kiểm một đáp án và tìm đáp án, làm nền để hiểu P và NP.
Mỗi bạn viết hai câu: một câu về việc kiểm đáp án cần bao nhiêu bước, một câu về việc tìm đáp án phải thử bao nhiêu khả năng. Hai câu phải có số.
Hãy tạo một bài tổng tập con: 20 số nguyên dương và một mục tiêu, sao cho có ít nhất một tập con có tổng đúng bằng mục tiêu. Đừng nói đáp án. Sau khi tôi nói “đã thử xong”, hãy đưa một đáp án để tôi tự kiểm.
Điểm cần nhấn mạnh sau hoạt động: kiểm nhanh không có nghĩa là tìm nhanh. Chuyện có cách tìm nhanh hay không chính là câu hỏi P và NP.