Blog Khoa Học Máy Tính

Có ba khả năng trả lời câu hỏi P chọi NP: (a) P = NP, (b) P chọi NP không quyết định được, nghĩa là độc lập với hệ thống, (c) P = NP hoặc P khác NP tùy theo ta chọn hệ tiên đề nào (tương tự như continuum hypothesis), và (d) P khác NP. (Bài báo của Micheal Sipser [30] là tham khảo tốt cho tình trạng hiện tại của câu hỏi này.)

Nếu (a) đúng thì cả chục nghìn vấn đề NP-đầy đủ có giải thuật đa thức để giải, mật mã khóa công cộng (public key cryptography) là vô vọng, vân vân. Các giao thức (protocol) bảo mật trên Internet hiện nay đều ít nhiều dựa vào mật mã khóa công cộng, nếu P = NP thì các giao dịch tiền tệ trên Internet đều cực kỳ bất ổn. Nếu P = NP thì hàng nghìn hàng vạn các nhà khoa học, toán học, kỹ sư máy tính trong hơn năm chục năm qua đã bỏ qua một ý tưởng căn bản nào đó có thể giải một trong số cả chục nghìn bài toán NP-đầy đủ. Chuyện này quá hy hữu. Vì thế, khả năng (a) rất khó xảy ra.

Các khả năng (b) và (c) liên quan đến trạng thái logic của vấn đề (thay vì tính thuật toán của nó). Scott Aaronson [1] có một bài báo tổng quan rất hay, thảo luận các khả năng này. Kết luận chung là các khả năng này rất khó xảy ra. Một tham khảo thú vị là nghiên cứu của Razborov và Rudich [27] năm 1993, trong đó các tác giả đưa bằng chứng cho thấy: “có lẽ lý do mà chứng minh P != NP rất khó là tại vì … P != NP !!!” Ta sẽ thảo luận kỹ hơn về kết quả “oái oăm” này vào dịp khác.

Như vậy, khả năng cuối cùng là P != NP, và đa số khoa học gia đều tin vào khả năng này. Thế ta phải làm gì nếu P thật sự khác NP? Ta thử liệt kê vài hướng đi hiện nay:

• Có lẽ mô hình máy Turing không phải là mô hình tính toán mạnh nhất. Điều này có nghĩa là ta phải thiết kế các máy tính theo kiểu khác, dựa trên một nguyên tắc hoàn toàn khác với nguyên tắc thiết kế hiện tại (với bộ vi xử lý, bộ nhớ, bus, thiết bị ngoại vi, vân vân). Đã có vài đề cử, trong đó quan trọng nhất là tính toán lượng tử (quantum computing, [25]), và tính toán sinh học (biological computing) [2]. Công trình đột phá của Peter Shor [28,29] cho thấy ta có thể phân tích một số nguyên ra thừa số (factorization) trong thời gian đa thức với một máy tính lượng tử. Bài toán này là một trong số rất ít các bài toán trong NP mà ta không biết là nó ở trong P hay là NP-đầy đủ. Ngoài bài báo của Peter Shor, thật sự vẫn chưa có bằng chứng nào ủng hộ khả năng là ta có thể giải các bài toán NP-đầy đủ trong thời gian đa thức với máy tính lượng tử. Tình hình với máy tính sinh học còn tệ hơn.
• Trong hướng đi thứ hai, ta chấp nhận rằng các bài toán NP-đầy đủ không thể giải được nhanh bằng các máy tính vật lý (bất kể mô hình vật lý nào). Đến đây thì có vài nhánh nghiên cứu khác:
  • Tìm cách hiệu quả nhất (dù là trong thời gian không đa thức) để giải các bài toán này. Các nghiên cứu về quy hoạch nguyên (integer programming) là một ví dụ tốt.
  • Trong thời gian đa thức, tìm lời giải càng gần tối ưu càng tốt. Đây là hướng đi của các giải thuất xấp xỉ (approximation algorithms), một hướng rất quan trọng trong khoa học máy tính hiện đại.
  • Một hướng khác cũng quan trọng không kém là dùng các giải thuật ngẫu nhiên hóa (randomized algorithms). Ta có thể tìm lời giải tối ưu trong thời gian kỳ vọng là đa thức (expected polynomial time), hoặc tìm lời giải với giá kỳ vọng (expected cost) gần tối ưu trong thời gian đa thức.

Tất cả các khả năng và hướng đi trên đưa chúng ta đến các phương trời mới của khoa học máy tính, toán học và vật lý, là các bước tiến quan trọng cho quá trình tìm hiểu vũ trụ và các quy luật hoạt động của tự nhiên (trong đó tính toán là một quá trình căn bản).

Người mở một trong những cánh cửa quan trọng nhất chính là Cantor!

[1] S. Aaronson, Is P versus NP formally independent?, Bulletin of the European Association for Theoretical Computer Science, 81 (2003).

[2] L. M. Adleman, Computing with DNA, Scientific American, 279 (1998), pp. 54–61.

[25] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000.

[27] A. A. Razborov and S. Rudich, Natural proofs, J. Comput. System Sci., 55 (1997), pp. 24–35. 26th Annual ACM Symposium on the Theory of Computing (STOC ’94) (Montreal, PQ, 1994).

[28] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26 (1997), pp. 1484–1509.

[29] _________, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Rev., 41 (1999), pp. 303–332 (electronic).

[30] M. Sipser, The history and status of the p versus np question, in STOC ’92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, ACM Press, 1992, pp. 603–618.

Chủ đề: Lý thuyết tính toán |