(+84) 463.28.7979

HP và thách thức thiên niên kỷ


Tháng 8 vừa qua là một tháng đáng nhớ với nhiều sự kiện, đối với người Việt Nam nói riêng, bên cạnh những sự kiện truyền thống chúng ta đón mừng một niềm vinh dự và tự hào lớn khi GS Ngô Bảo Châu được trao huy chương Fields – giải thưởng Toán học cao quí nhất dành cho một cá nhân được trao tặng 4 năm một lần.

Vinay Deolalikar vẫn chưa giải quyết được vấn đề P và NP


Tuy nhiên đối với giới Toán học và Khoa học máy tính nói riêng thì còn một sự kiện chấn động khác, thậm chí còn lớn hơn cả công trình về Bổ đề cơ bản của giáo sư Châu cách đó hơn 1 năm khi một cán bộ thuộc phòng nghiên cứu của Hewlett-Packard (HP) – Vinay Deolalikar tuyên bố đã tìm được lời giải cho một trong 6 bài toán thiên niên kỷ, một vấn đề đáng giá cả triệu đô la.

P hay NP là một trong 7 bài toán thiên niên kỷ do viện toán học Clay đề xuất cùng giải thưởng 1 triệu đô la sẽ trao tặng cho bất cứ ai giải được một trong 7 bài toán này. Trong các năm 2003 – 2004, giả thuyết Poincare – một trong những bài toán trên đã được chứng minh bởi nhà toán học người Nga G. Perelman, ông lập tức được trao huy chương Fields vào năm 2006 cùng giải thưởng 1 triệu đô la từ viện Clay, tuy nhiên Perelman đã từ chối mọi lời tung hô, lui về ở ẩn và hầu như cắt đứt liên hệ với cộng đồng toán học quốc tế. Một cách tổng quát, 7 bài toán lớn này bao trùm khắp các lĩnh vực cơ bản của Toán học nói riêng và khoa học cơ bản nói chung, vì thế tầm quan trọng của mỗi bài toán là rất lớn. Vấn đề P hay NP liên quan chặt chẽ tới lĩnh vực khoa học máy tính đặc biệt là lý thuyết mã hóa thông tin và cơ sở các thuật toán. Cách đặt vấn đề của câu hỏi này là, tập hợp các bài toán và câu hỏi có thể dễ dàng tìm ra câu trả lời (được gọi là lớp P hay viết tắt là P) là trùng với tập hợp các bài toán và câu hỏi có thể dễ dàng kiểm chứng câu trả lời, được giả định là đã biết trước, (gọi là lớp NP hay NP – viết gọn) hay không? Người ta thường mô tả bài toán này dưới dạng “P = NP” hoặc “P khác NP”. Vấn đề này được đặt ra bởi nhà toán học người Mĩ, Stephen Cook vào năm 1971. Hầu hết các nhà toán học tin rằng P khác NP, lấy một ví dụ về vấn đề P và NP như sau: Chẳng hạn tôi có hai con số rất lớn (chính xác thì chúng phải là nguyên tố), ví dụ mỗi số cỡ vài tỷ tỷ tỷ gì đó, tôi đem nhân chúng với nhau, kết quả này là một con số rất lớn khác, tôi gọi là A. Việc kiểm tra lại tích hai số này có đúng là A không khá đơn giản với những máy tính mạnh và vì vậy, nó là vấn đề thuộc lớp NP. Tuy nhiên, giả sử ban đầu tôi có số A, việc tìm lại hai số mà tôi đã nhân để ra A lại vô cùng phức tạp ngay cả khi máy tính chạy với tốc độ ánh sáng thì với những số A lớn, đôi khi phải mất hàng trăm thậm chí là hàng tỷ năm tính toán liên tục – một điều không tưởng, như vậy vấn đề này không thuộc lớp P.

Tại sao “P hay NP” lại quan trọng? Đó là vì ngày nay hệ thống thông tin toàn cầu đều được phát triển trên một niềm tin đó là P khác NP, nói cách khác, toàn bộ hệ thống an ninh, bảo mật và mã hóa – điều sống còn trong lĩnh vực ngân hàng, tài chính, an ninh quốc phòng và hầu như cả mạng internet, đều được xây dựng trên các thuật toán dựa trên cơ sở rằng P khác NP và nếu sự thật không phải vậy, rằng P = NP thì toàn bộ hệ thống khổng lồ trên đã được tạo lập trên nền móng bằng cát và có thể sụp đổ bất cứ lúc nào, vì chắc chắn theo thời gian, nếu P=NP người ta sẽ tìm ra các thuật toán để phá mọi loại mã hóa một cách nhanh chóng, khi đó nền tài chính toàn cầu – cơ sở của thế giới hiện đại cùng những thông tin an ninh quốc phòng và vô số vấn đề liên quan sẽ trở thành “miếng mỡ treo miệng mèo” cho giới hacker và những kẻ phá hoại. Tầm quan trọng của bài toán P hay NP có thể nói là sống còn trong xã hội ngày nay khi mọi thứ đều dần được máy tính hóa, cũng có thể các nhà phát triển đã rất “liều” khi xây dựng cả một hệ thống đồ sộ trên một định đề chưa được chứng minh hay bác bỏ, tuy vậy, hầu như mọi người đều tin rằng P khác NP.

Trở lại với thông tin của về lời giải của Vinay mà theo bản tóm tắt được đưa lên trang arXiv.org là dài tới hơn 100 trang, đã có rất nhiều người nghi ngờ về kết quả này, lịch sử cho thấy hàng năm viện Clay luôn nhận được hàng chục bài báo từ khắp nơi trên thế giới gửi về với nội dung giải quyết một trong những vấn đề hóc búa này và tất nhiên, tất cả đều không hoặc ít có giá trị do nhầm lẫn. Tuy nhiên, bài báo của Vinay lại được chính bản thân S. Cook đánh giá cao mặc dù ông vẫn chưa khẳng định hay phủ định gì về bài báo. Trong thời gian này tên tuổi của Vinay được lan truyền nhanh chóng và tràn ngập internet, một vài diễn đàn Việt Nam cũng đăng tin nhưng đáng tiếc việc đăng tin không cẩn thận đã khiến nhiều người hiểu lầm rằng thách đố thiên niên kỷ trị giá 1 triệu đô đã bị khuất phục. Đúng một tuần sau, trên blog của Terence Tao, một trong những nhà toán học trẻ xuất sắc nhất hiện nay – giải Fields năm 2006, đã đưa ra một thông báo rằng hóa ra cái mà nhân viên của HP làm được không phải là vấn đề P hay NP mà là một vấn đề tương tự nhưng dễ hơn rất nhiều – dễ đến mức “lời giải của nó có thể chỉ vỏn vẹn nửa trang báo” – Tao nói.

Như vậy bài toán P hay NP vẫn còn là mở và cơ sở cho toàn bộ hệ thống thông tin điện tử toàn cầu vẫn chưa được khẳng định an toàn dù rằng việc P = NP đã gần như được công nhận trong trực giác của hầu hết những nhà khoa học liên quan. Dẫu thế, cũng như Bổ đề cơ bản của Langlands, dù được tin là đúng trong suốt hơn 30 năm tồn tại nhưng chỉ đến khi Ngô Bảo Châu đưa ra được chứng minh trọn vẹn vào năm 2008 (mất 1 năm để các chuyên gia kiểm chứng là đúng vào năm 2009 và công trình này trở thành một trong những khám phá khoa học nổi bật nhất của năm do tạp chí Times bình chọn), giới Toán học mới thở phào nhẹ nhõm để tiếp tục trên một hành trình còn gian nan hơn – tiến thẳng vào chương trình Langlands khi hòn đá tảng, bổ đề cơ bản (Fundamental Lemma) đã được dẹp bỏ.

Theo TT

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>