Chung qui chỉ tại Cantor (10)

 

Bài toán nào nằm trong P được xem là bài toán "dễ", còn lại là các bài toán khó. Lớp P chỉ có thể được định nghĩa chính xác bằng toán học nếu ta có một mô hình toán học cho khái niệm giải thuật. Dĩ nhiên mô hình này không gì khác hơn là máy Turing.

Máy Turing còn có một dạng bất định, gọi là máy Turing bất định (non-deterministic Turing machine, ký hiệu là NTM). Máy Turing bình thường còn được gọi là máy Turing xác định (deterministic Turing machine, hay DTM). Máy NTM cũng tương tự như DTM, chỉ khác ở chỗ máy NTM có thể chọn bước thực thi kế tiếp tùy hỉ trong một tập cho trước các lệnh. Ta sẽ định nghĩa rõ ràng hơn trong phần tới.

Về mặt trực quan thì rõ ràng NTM có vẻ mạnh hơn DTM. Tuy vậy, chứng minh điều này không dễ dàng chút nào. Lớp các bài toán giải được bằng NTM được gọi là lớp NP. Câu hỏi rằng liệu NTM có thật sự mạnh hơn DTM hay không chính là câu hỏi trung tâm của khoa học máy tính hiện nay. Nói cách khác: "P có bằng NP không?"

Trong cùng tinh thần của các bài toán Hilbert, viện toán Clay (Clay Mathematics Institute) đã treo giải thưởng một triệu đô la cho ai giải được một trong 7 bài toán chưa có lời giải của thế kỷ 20, một trong 7 bài toán này chính là câu hỏi P=NP?. (Một bài khác chính là bài toán số 8 của Hilbert: giả thuyết Riemann).

Năm 1971, Stephen Cook [7] chứng minh rằng có các vấn đề trong lớp NP mà tất cả các vấn đề khác trong NP có thể chuyển giản (reduced) về được trong thời gian đa thức. Phép chuyển giản này có thể được mô tả đại khái như sau: nếu vấn đề A có thể chuyển giản được về vấn đề B trong thời gian đa thức, thì nếu ta giải được B trong thời gian đa thức ta sẽ giải được A trong thời gian đa thức. Theo nghĩa thời gian đa thức thì vấn đề B khó hơn hoặc bằng A. Vì thế, các vấn đề mà Cook đề cập là các vấn đề khó nhất trong lớp NP. Các vấn đề này gọi là các vấn đề NP-đầy đủ. Cook chứng minh rằng sat, 3-sat , và subgraph isomorphism là NP-đầy đủ. Độc lập với Cook, Leonid Levin cũng có một bài báo năm 1973 [22] với kết quả tương tự.

Năm 1972, Richard Karp [18] chứng minh rằng 20 vấn đề tự nhiên khác cũng NP-đầy đủ, như Vertex Cover, Euclidean TSP, Clique, Independent Set, ... Năm 1972, Donald Knuth [20, 21] góp phần định ra các thuật ngữ của ngành này như ta thấy ngày nay, vì lúc đó ông đang viết phần 4 của bộ sách kinh điển "nghệ thuật lập trình máy tính". Quyển sách của Garey và Johnson [12] có thảo luận sơ qua về quá trình thay đổi thuật ngữ trong thời gian đó.

Hầu hết những nhà khoa học ta vừa nhắc đến đều được giải Turing (giải thưởng tương đương với giải Nobel cho khoa học máy tính): Rabin, Hartmanis và Stearns, Blum, Cook, Karp, và Knuth.

[7] S. A. Cook, The complexity of theorem-proving procedures , in Conference Record of the Third Annual ACM Symposium on the Theory of Computing, 1971, pp. 151–158.

[18] R. M. Karp, Reducibility among combinatorial problems , in Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, pp. 85–103.

[20] D. Knuth, Postscript about np-hard problems , SIGACT News, 6 (1974), pp. 15–16.

[21] _________, A terminological proposal, SIGACT News, 6 (1974), pp. 12–18.

 

[22] L. Levin , Universal search problems (in russian) , Problemy Peredachi Informatsii, 9 (1973), pp. 265–266. English translation in Trakhtenbrot, B. A.: A survey of Russian approaches to Perebor (brute-force search) algorithms. Annals of the History of Computing, 6 (1984), pp 384–400.