[membersonly]

Trong loạt bài này, ta 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á một triệu USD [20] và danh tiếng sẽ đ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 hẳn 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.

Quan trọng hơn hết, tôi hy vọng 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à độ phức tạp (computational and complexity theory). Hành trình của ta sẽ ghé qua những vấn đề căn bản nhất mang đậm tính triết học trong lý thuyết khoa học máy tính.

1. Giải thuật và độ phức tạp

"In P or not in P, that’s the questions!"

Đọc các quyển sách về phân tích và thiết kế giải thuật (như [10]), ta thấy có rất nhiều 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ụ: Sắp xếp thứ tự (sort) n số cần thời gian O(nlgn), tìm đường đi ngắn nhất (shortest path) trong một đồ thị G = (V,E) cần khoảng chừng O(|V |lg|V | + |E|), biến đổi Fourier nhanh (FFT) cần O(nlgn), …

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), … (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 khác).

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ó những vấn đề không tự nhiên. Đó là những 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 [11], 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. Ta muố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 (v_i,w_i ∈ Z+). 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 traveling 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ố đúng một lần và quay trở về thành phố ban đầu.

Giả sử bạn đi làm cho một công ty nào đó, sếp giao nhiệm vụ viết một chương trình tốt, chạy nhanh, để giải một bài toán vào loại rất khó này, bạn sẽ làm gì? Ta thử ghi ra đây một vài khả năng:

1. Hỏi giáo sư dạy giải thuật (và ông ta bí);
2. Bảo với sếp là “tôi chịu thôi” (và bị mất việc);
3. Ném 6 tháng cuộc đời vào “sọt rác” để tìm giải thuật hiệu quả, và sau đó quay lại khả năng 2;
4. Tìm giải thuật cơ bắp (brute-force) tốn khoảng vài chục thế kỷ chạy mới xong (mất việc và mất mặt);
5. Chứng minh cho sếp thấy là bài toán này không có giải thuật hiệu quả (cận dưới thời gian chạy là một hàm mũ chẳng hạn). Khả năng này rất khó xảy ra, kinh nghiệm cho thấy chứng minh những điều tương tự là cực kỳ khó. Với tất cả các bài toán loại này, cận dưới tốt nhất người ta biết là Ω(n): vô dụng.
6. Chứng minh rằng bài toán sếp cho cũng khó như hàng chục ngàn bài toán khác chưa ai biết giải.

A ha, khả năng số 6 nghe có vẻ được, nhưng cũng có vẻ lừa phỉnh, vì ta thật ra không giải quyết thẳng vào vấn đề, mà “bán cái” cho nửa thế kỷ nghiên cứu của vô vàn người khác!

Nhưng làm thế nào ta chứng minh một điều như vậy? Thế nào gọi là khó? Thế nào là cái này khó tương đương cái kia? Về mặt trực quan thì có thể hiểu như sau: một bài toán khó là bài toán không giải được trong thời gian đa thức; hai bài toán khó tương đương nhau nếu giải bài này một cách hiệu quả thì cũng giải được bài kia một cách hiệu quả và ngược lại. Còn để trả lời nghiêm túc về mặt toán học, thì ta phải xem lại định nghĩa khái niệm giải thuật và các thứ liên quan.

Ta sẽ phải quay lại bánh xe lịch sử. Hành trình này đưa ta đến với Cantor, Russell, Hilbert, Godel, Church, Turing, Cook/Levin, Karp và các ý tưởng tuyệt vời của họ.

[/membersonly]