Quyển Computers and Intractability: A Guide to the Theory of NP-Completeness của Garey và Johnson là tham khảo kinh điển về lý thuyết NP-đầy đủ. Trong 30 năm qua, Johnson vẫn tiếp tục viết các NP-complete columns để cho ta biết các cập nhật mới nhất về các bài toán NP-đầy đủ.
Hồi xưa, ta có thể viết một bài báo chứng minh một bài nào đó là NP-Hard. Nay thì 99.9% các kết quả loại này chỉ là một bổ đề trong phần appendix của một bài báo. Các chứng minh NP-hardness đã trở thành routine như kiểu tính tích phân (mặc dù tính tích phân không phải lúc nào cũng đơn giản!).
Ngày nay, khi đối chọi với một bài toán mới, để có thể đăng tải kết quả thì ngoài chuyện chứng minh là nó NP-hard ta thường phải làm thêm 2 việc nữa: (1) tìm một thuật toán xấp xỉ tốt, và (2) chứng minh rằng xấp xỉ bài này đến một tỉ lệ nhất định cũng NP-hard nốt. Công việc (2) được gọi là chứng minh “hardness of approximation”. (Ta có thể thay giả thiết P khác NP bằng một giả thiết khác trong complexity theory. Giả thiết “hot” nhất hiện nay là Unique Game Conjecture. Xem thêm ở Khot’s homepage, và bài này, bài này nữa.) Kỹ thuật chính để chứng minh các kết quả loại này là dùng Probabilistically Checkable Proofs.
Lẽ tự nhiên, column mới nhất của David Johnson nói về các kết quả loại này — một bước nhảy lượng tử từ NP-hardness lên NP-hardness of approximation. Muốn biết chi tiết hơn, đọc các bài [Trevisan 2004] và [Khot 2005].