P ≠ NP? Một Bài Toán Triệu Đô, Hay Một Hài Kịch Tri Thức?

Hơn nửa thế kỷ qua, giới khoa học máy tính và toán học bị ám ảnh bởi một câu hỏi nghe đơn giản mà lạ lùng đẹp: nếu ta có thể kiểm tra một lời giải rất nhanh, liệu ta có thể tìm ra lời giải nhanh tương tự không? Đó là câu hỏi P so với NP. Nó đã đi từ phòng seminar tới báo chí đại chúng, từ lớp học đại cương tới những quán cà phê công nghệ; và nhờ giải thưởng một triệu đô la của Clay Institute, nó trở thành biểu tượng của thời đại: một “ngọn Everest” cho bất kỳ ai trót yêu lập luận.

Nhưng sự đẹp đẽ của câu hỏi đôi khi chính là cái bẫy. Bởi vì ẩn dưới khẩu hiệu “kiểm tra nhanh có đồng nghĩa với tìm nhanh” là hai kiểu công việc tinh thần khác nhau đến mức khó so sánh: tạo sinh và xác minh. Khi một câu hỏi gom hai thế giới ấy vào cùng một thước đo thời gian, ta nên hỏi lại: liệu đây có phải là một bài toán thuần túy, hay là một ảo ảnh logic được kể bằng ngôn ngữ của toán học?

Hãy hình dung ba tình huống quen thuộc.

Viết một tiểu thuyết và đọc một tiểu thuyết. Vẽ một bức tranh và chấm điểm bức tranh. Khai phá một chứng minh và rà soát một chứng minh. Ở vế đầu, ta phải dò dẫm, chọn đường, chịu những ngõ cụt; ở vế sau, ta đi theo một lộ trình đã có, so chiếu từng bước với tiêu chí sẵn có. Hai việc ấy đều thông minh, nhưng khác loại.

P – lớp các bài toán “giải được nhanh” – mang tinh thần tạo tác: phải xây lời giải. NP – lớp các bài toán “kiểm chứng được nhanh” – mang tinh thần thẩm định: được cho một ứng viên lời giải và ta chỉ việc kiểm. Khi hỏi “tạo tác có thể nhanh như thẩm định không?”, ta đang ép hai khung tham chiếu nhận thức vào cùng một rãnh đo tốc độ. Đó là một so sánh hấp dẫn, song rất có thể là một so sánh sai thể loại.

Trực giác thường đứng về phía P ≠ NP. Lý do dễ hiểu: kiểm tra cho phản hồi nhị phân (đúng/sai); tạo sinh đòi tín hiệu định hướng (đi đâu tiếp theo?). Một trình kiểm toán có thể đánh dấu sai, nhưng nó không mách ta con đường sửa sai. Một trình biên dịch báo “lỗi dòng 27”, nhưng tại sao dòng 27 sai và sửa thế nào lại là công việc khác hẳn.

Trong nhiều họ bài toán, những trường hợp khó nhất cũng là những trường hợp “ngẫu nhiên” nhất – nơi không có mô hình lộ diện để bấu víu. Ngược lại, hễ ở đâu lộ ra quy luật, đối xứng, khả năng nén thông tin, khả năng phân rã thành phần… thì ở đó xuất hiện thuật toán tốt hơn. Cảm giác “có cấu trúc thì dễ, vô cấu trúc thì khó” không phải bịa. Nó chỉ ra một trục nội dung – từ có mẫu đến không mẫu – mà trên đó độ khó dịch chuyển.

Nhưng trực giác, dù mạnh, không thay được một chứng minh.

Nếu đây chỉ là một bài toán khó thông thường, hẳn ta đã thấy một chuỗi kỹ thuật tiến sát đích. Thay vào đó, lịch sử P vs NP nổi tiếng với các rào cản: những kết quả chỉ ra cả một họ phương pháp không thể dùng để giải quyết câu hỏi. Chúng cho thấy vấn đề không chỉ “khó”, mà khó theo cấu trúc.

Relativization: nhiều lập luận vẫn đúng ngay cả khi ta thêm một “hộp đen” vào mô hình tính toán; và trong bối cảnh đó ta có cả thế giới nơi P=NP và thế giới nơi P≠NP. Một phương pháp “tương đối hóa” như vậy khó lòng chốt câu trả lời phổ quát.

Natural proofs: một lớp kỹ thuật chứng minh rất tự nhiên tỏ ra quá mạnh – mạnh đến mức nếu thành công, nó sẽ phá hủy các giả định mật mã đang trụ vững. Điều này gợi ý: con đường quen tay có thể không dẫn tới đâu.

Algebrization: ngay cả khi “nâng” lập luận sang ngôn ngữ đại số, vết nứt vẫn còn đó.

Ba rào cản khác nhau, chặn ba con đường tưởng như hợp lý. Ta không tiến gần đỉnh núi hơn: có cảm giác chính ngọn núi này không cho leo bằng các lối mòn thông thường.

Ta đã từng chứng kiến trong toán học: có những mệnh đề đúng hình thức nhưng không thể quyết trong một hệ tiên đề tiêu chuẩn. Chúng không vô nghĩa; chúng chỉ “nằm ngoài tầm với” của bộ công cụ hiện có. P vs NP có thể thuộc loại ấy – không phải vì nó mơ hồ, mà vì nó bắc cầu giữa hai cấp độ nhận thức khác loại: tạo sinh và thẩm định. Một hệ tiên đề toán học thuần cú pháp có thể không đủ ngôn ngữ để hàn gắn khoảng cách đó.

Nói cách khác: không phải ta thiếu thiên tài, mà ta thiếu khung.

Một triệu đô la giúp câu hỏi nổi tiếng, nhưng lý do sâu hơn là: P vs NP đã tạo ra một ngành. Từ nó, ta có lý thuyết độ phức tạp, có hàng loạt kỹ thuật phân tích thuật toán, có cả nền mật mã học hiện đại dựa trên giả định “tìm thì khó, kiểm thì dễ”. Những “sản phẩm phụ” ấy – thuật toán xấp xỉ, mô hình ngẫu nhiên, kỹ thuật học máy chịu ràng buộc… – tạo ra giá trị thực cho khoa học lẫn công nghiệp.

Không loại trừ khả năng đây cũng là một chiến lược truyền thông khôn ngoan: một câu hỏi đẹp, một giải thưởng rõ ràng, một thông điệp dễ nhớ. Nhưng “khôn ngoan” không đồng nghĩa với lừa dối. Cũng như giải Fields hay giải thưởng Millennium khác, nó là cách hệ tri thức tự kể câu chuyện của mình với công chúng, kéo người trẻ vào, gom tài nguyên và chú ý về một số điểm tựa quan trọng.

Nếu mai này ai đó chứng minh được “không thể quyết trong hệ tiên đề hiện tại”, câu hỏi vẫn đã hoàn thành sứ mệnh: nó sinh ra một sinh quyển tri thức.

Thứ nhất, hãy phân biệt cẩn thận giữa bài toán cụ thể và tuyên bố phổ quát. Với bài toán cụ thể, ta có thể đo lường, chứng minh, cải thiện. Với tuyên bố “mọi bài toán kiểm được nhanh thì giải cũng nhanh”, ta bước vào địa hạt siêu hình của tri thức – nơi so sánh hai kiểu hoạt động tâm trí bằng một thước chung có thể là tham vọng quá mức.

Thứ hai, thay vì săn lùng một lời giải tất cả trong một, ta có thể chấp nhận một bản đồ nhiều miền: ở đâu có mẫu, có đối xứng, có khả năng phân rã – ở đó thuật toán tốt nở rộ; ở đâu mẫu bị che khuất – ở đó bài toán kháng cự. Khi ngôn ngữ “mẫu – vô mẫu” trở nên sắc bén, nhiều tranh cãi quanh P vs NP tự nhiên hạ nhiệt: ta chuyển từ thắng–thua tuyệt đối sang độ đo và cơ chế.

Thứ ba, khoa học đôi khi lớn lên nhờ những câu hỏi không đóng. Chúng giống các cực từ: không phải để chạm tới, mà để sắp xếp đường sức. P vs NP có thể là một cực như thế.

P vs NP là một tấm gương. Khi soi vào nó, ta thấy bản chất của lao động trí tuệ: sự khác biệt giữa tạo tác và thẩm định; sức mạnh và giới hạn của hình thức hóa; cách cộng đồng khoa học kiến tạo ưu tiên và câu chuyện cho chính mình. Nếu ngày mai có ai chứng minh P=NP, thế giới mật mã sẽ chao đảo, các nhà khoa học sẽ hò reo, và báo chí sẽ có một mùa gặt. Nếu có ai chứng minh P≠NP, nhiều giả định sẽ được “đóng dấu chính thức”, và một chương lịch sử sẽ khép lại. Còn nếu điều hợp lý hơn xảy ra – rằng câu hỏi không thể quyết trong khung tiên đề hiện tại – thì đó vẫn là một chiến thắng trí tuệ: ta biết rìa biên của công cụ mình ở đâu.

Trong lúc chờ những tin tức ấy – hay chấp nhận rằng chúng sẽ không đến – tốt hơn cả là tiếp tục làm điều đã chứng tỏ hữu ích: giải những bài toán cụ thể, đo được; săn mẫu và gọi tên mẫu; nhận ra khi nào nên tìm đường tắt và khi nào phải đi bộ qua sa mạc. Một câu hỏi lớn đôi khi không phải để có câu trả lời, mà để nhắc ta rằng tri thức cũng cần kỷ luật của khiêm nhường: biết mình có thể hỏi được gì, bằng thứ ngôn ngữ nào, và ai là người thật sự hưởng lợi từ hành trình cứ tưởng là leo núi, mà hóa ra là mở đường.