Chung qui chỉ tại Cantor (1)

Trong loạt bài này, tôi sẽ duyệt qua các ý tưởng lớn và lịch sử xoay quanh một trong những bài toán quan trọng nhất của thế kỷ 21: bài toán "P chọi NP" ( P versus NP). Câu trả lời đáng giá 1 triệu USD và danh tiếng đi vào lịch sử khoa học. Cũng như bài toán Fermat lớn, bản thân câu trả lời cho bài "P chọi NP" không quan trọng bằng các kỹ thuật, hướng nghiên cứu, ngành nghiên cứu mới mà người ta khám phá ra để đi đến câu trả lời. (Kiểu ngón tay và mặt trăng của Phật Giáo.)

Quan trọng hơn hết, tôi hy vọng loạt bài này đóng vai trò giới thiệu và khích lệ các bạn đến với một nhánh trung tâm của khoa học máy tính: lý thuyết tính toán và sự phức tạp ( computational and complexity theory). Hành trình của ta sẽ ghé qua những vấn đề mà máy tính không giải quyết được, như đã hứa.

In P or not in P, that's the question!

Đọc các quyển sách về phân tích và thiết kế giải thuật (như CRLS), ta thấy rất nhiều các bài toán thú vị, cực kỳ hữu dụng và đẹp, mà lại có thể giải được trong thời gian đa thức. Ví dụ: xếp thứ tự (sort) n số cần thời gian O(n lg n), tìm đường đi ngắn nhất ( shortest path) trong một đồ thị G=(V,E) cần khoảng O(VlgV+E), biến đổi Fourier ( FFT) cần O(n lg n), vân vân.

Các vấn đề này đều là các vấn đề then chốt và tự nhiên của các ngành khoa học kỹ thuật như mạng máy tính (bài toán tìm đường), điện/điện tử và xử lý tín hiệu (FFT), cơ sở dữ liệu (xếp thứ tự các records), vân vân. (Các ví dụ nêu ra chỉ mang tính minh họa, các vấn đề tìm đường, xếp thứ tự, FFT, ... có cực kỳ nhiều ứng dụng!)

Có lẽ phải giải thích một chút tôi muốn nói gì bằng chữ tự nhiên. Có các vấn đề không tự nhiên. Đó là các vấn đề mà người ta tạo ra chỉ để chứng minh một mệnh đề nào đó hoặc giải quyết một ứng dụng nho nhỏ nào đó, mà không có ứng dụng ở chỗ nào khác. Khi một nhánh nghiên cứu còn non trẻ, sẽ có nhiều vấn đề không tự nhiên kiểu này. Có rất nhiều các bài báo chuyên ngành giải quyết các bài toán đi vào quên lãng ngay sau khi bài báo được đăng. Khi nào có thời gian ta sẽ nói thêm về đề tài này, bản thân tôi nghĩ là nó rất quan trọng cho những ai bắt đầu làm nghiên cứu. Trong giới hạn của bài này, ta cứ nghĩ về "vấn đề tự nhiên" như một vấn đề có nhiều ứng dụng các nơi.

Đến đây nảy ra câu hỏi thú vị: "có thể nào tất cả các vấn đề tự nhiên đều giải được trong thời gian đa thức?" Sau hơn nửa thế kỷ của nghiên cứu giải thuật, về căn bản là ta vẫn chưa trả lời được câu hỏi này. Dường như có rất nhiều bài toán tự nhiên rất khó (theo nghĩa là không có giải thuật hiệu quả để giải). Có khoảng một chục nghìn bài toán tự nhiên kiểu này, thách đố hơn nửa thế kỷ nghiên cứu của các kỹ sư và khoa học gia hàng đầu. Ngược lại, cũng không ai chứng minh được bất kỳ bài nào trong số đó là không có giải thuật hiệu quả để giải.

Ta hãy xem thử một vài bài toán kiểu này:

• Vertex Cover: môt vertex cover của một đồ thị G=(V,E) là một tập S các đỉnh sao cho tất cả các cạnh của G đều kề với một đỉnh trong S. Bài toán này cần tìm vertex cover với kích thước nhỏ nhất.
• 01-Knapsack: một anh ăn trộm tìm được n vật quý, vật quý thứ i nặng w_i cân và đáng giá v_i đồng. Anh ta lại chỉ có thể vác tối đa là W cân. Hỏi: anh ta phải lấy những vật nào để có được tổng giá trị lớn nhất.

Euclidean Travelling Salesman (Euclidean TSP): tìm đường ngắn nhất cho một anh bán hàng đi qua n thành phố, mỗi thành phố một lần và trở về thành phố đầu tiên