Chung qui chỉ tại Cantor (9)

"Các bài toán có và không có các giải thuật tốt để giải đều rất đáng quan tâm … Tôi giả định (conjecture) rằng không có giải thuật tốt nào để giải bài toán chàng bán hàng rong (traveling salesman). Các lý do của tôi cũng giống như lý do cho các giả định toán học khác: (1) chuyện đó có khả năng xảy ra, và (2) tôi không biết."

[Jack Edmonds, 1966]

Trong bài trước, ta đã nói đến bài toán dừng của Turing và bài toán trong giải tích lambda của Church, các bài toán không có giải thuật nào giải được. Đây là một trong những kết quả cực kỳ quan trọng của khoa học máy tính lý thuyết, nhất là về mặt triết học. Khả năng của máy tính đúng là có giới hạn! Khẳng định này dường như có vẻ tầm thường, ai chẳng nghĩ là khả năng của một cái máy chỉ có một giới hạn nhất định nào đó.

Không hẳn như thế. Thứ nhất, bài toán dừng là một bài toán rất cụ thể, vạch một ranh giới cụ thể cho giới hạn của máy tính. Kỹ thuật chứng minh này sẽ được dùng đi dùng lại cho các bài toán không quyết định được (undecidable problems) khác. Thứ hai, khi biết cái gì làm cho máy Turing có giới hạn, việc tìm một mô hình mạnh hơn mô hình máy Turing sẽ có đường đi rõ ràng hơn. Thứ ba, kể cả vũ trụ cũng có giới hạn, cho nên một giới hạn về mặt lý thuyết không hẳn là liên quan gì đến giới hạn thực tế. Bằng chứng là sự bùng nổ của khoa học máy tính và các công nghệ đi kèm trong vài chục năm qua và vài trăm, có lẽ vài ngàn năm tới. Điều này cho thấy ta cần phải nghiên cứu kỹ hơn bên trong cái giới hạn lý thuyết đó: nghiên cứu các bài toán có giải thuật để giải, và phân lớp chúng ra, xem giới hạn thực tế của máy tính là đến đâu.

Đầu những năm 60, các kỹ sư và khoa học gia bắt đầu chú ý rằng có các bài toán mà giải thuật cho chúng đòi hỏi rất nhiều thời gian chạy. Thời đó, thời gian chạy máy khá đắt tiền, tài nguyên tính toán thì ít ỏi. Người ta mới nghĩ đến việc nghiên cứu giải thuật bằng tổng số bước nó cần để giải một bài toán nhất định ( Micheal O. Rabin [5], Juris Hartmanis và Richard E. Stearns [6], Manuel Blum [7]). Ở Nga, năm 1959 Yablonski cũng đã có hơi hướng đề cập đến độ phức tạp giải thuật [8,9]. Trước đó, Kurt Gödel đã chú ý đến vấn đề này trong một lá thư gửi Jon von Neumann (khi đó đang dưỡng bệnh ung thư).

Ngành nghiên cứu giải thuật và độ phức tạp của chúng thật sự bắt đầu với Jack Edmonds và bài báo năm 1965 của ông với tựa đề "đường đi, cây, và hoa" [1]. Đóng góp chính của bài báo là một giải thuật thời gian đa thức cho bài toán maximum matching. Bài báo đó của Edmonds, và một bài khác của Alan Cobham [2] bắt đầu định nghĩa lớp P là lớp các bài toán có thể giải được trong thời gian đa thức. Bài toán nào nằm trong P được xem là bài toán "dễ".

[1] Edmonds, Jack, 1965, "Paths, Trees and Flowers", Canadian Journal of Mathematics, 17, Toronto, 449-467.

[2] Cobham, Alan, 1964, "The Intrinsic Computational Difficulty of Functions," Proceedings of the 1964 Congress for Logic, Mathematics, and Philosophy of Science, North-Holland, Amsterdam, 24-30.

[3] Levin, Leonid, 1973, "Universal search problems," Problemy Peredachi Informatsii, 9(3), 265-266; partial English translation in: B.A.Trakhtenbrot, 1984, "A Survey of Russian Approaches to Perebor (Brute-force Search) Algorithms," IEEE Annals of the History of Computing , 6(4), Los Alamitos, CA, 384-400.

[4] Cook, Stephen, 1971, "The Complexity of Theorem Proving Procedures," Proceedings of the Third Annual ACM STOC Symposium, Shaker Heights, Ohio, 151-158.

[5] M.O. Rabin, Degree of diflieutly of computing a function and a partial ordering of reeursive sets, Teeh. Rep. No. 2, Hebrew University, 1960.

[6] J. Hartmanis and Ẹ Stearns, On the computational complexity of algorithms, Transactions of the AMS 117, 285-306, 1965.

[7] Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967

[8] S. Yablonski, The algorithmic difficulties of synthesizing minimal switching circuits, Prob. lemy Kibernetiki 2, Moscow, Fizmatgiz, 75- 121, 1959; translation in Problems of Cybernetics 2, Pergamon Press, 401-457, 1961.

[9] S. Yablonski, On the impossibility of eliminating brute force search in solving some problems of circuit theory, Doklady, AN SSSR 124, 44-47, 1959