Giải được bài toán này, bạn sẽ có toàn bộ Bitcoin trên thế giới

11/07/2019 18:22
Giải được bài toán này, bạn sẽ có toàn bộ Bitcoin trên thế giới

Nếu thành công trong việc chứng minh P bằng NP, bạn sẽ kiếm được hàng tỷ USD. Nếu không thành công cũng tốt, ít nhất là các hệ thống mã hoá toàn cầu vẫn còn được đảm bảo an ninh.

P (giải nhanh chóng) so với NP (kiểm chứng nhanh chóng) là bài toán mở quan trọng trong lý thuyết khoa học máy tính. Có thể mô tả một cách đơn giản như sau: Nếu một bài toán có lời giải có thể kiểm chứng được nhanh chóng, liệu có thể tìm lời giải đó nhanh chóng hay không?

Chẳng hạn như trò chơi Sudoku, dù rất khó nhưng kiểm tra lại rất dễ (chỉ cần cộng lại các hàng, cột và đường chéo), đó chính là vấn đề.

P so với NP được Stephen Cook đưa ra năm 1971 trong bài báo nổi tiếng "The complexity of theorem proving procedures", được nhiều người xem là bài toán quan trọng nhất trong ngành khoa học máy tính.

Giai duoc bai toan nay, ban se co toan bo Bitcoin tren the gioi hinh anh 1
Sơ đồ hiển thị các lớp vấn đề cần phải chứng minh để P = NP. Ảnh: Behnam Esfahbod.

Đây cũng là một trong bảy bài toán thiên niên kỷ chọn bởi Viện Toán học Clay. Mỗi bài trong số bảy bài này có giải thưởng 1.000.000 USD cho lời giải đúng đầu tiên.

Lời giải bài toán P = NP sẽ cho biết liệu tất cả các bài toán trong NP, như bài toán tổng tập hợp con, đều có thuật toán thực thi trong thời gian đa thức. Nếu P ≠ NP, thì có nhiều bài toán trong NP (chẳng hạn như các bài toán NP - đầy đủ) có lời giải có thể kiểm chứng được trong thời gian đa thức (khoảng thời gian hữu hạn nào đó có thể tính toán được) nhưng không thể tìm ra một lời giải như vậy trong thời gian đa thức.

Bài toán mở ra kho vàng

Nhà khoa học máy tính Scott Aaronson đã giải thích tại bài giảng trong Phòng thí nghiệm quốc gia Los Alamos ở New Mexico, chứng minh P = NP sẽ mở ra một số khả năng hấp dẫn.

Nếu ai đó chứng minh được P = NP, điều đầu tiên họ làm là lấy 200 tỷ USD giá trị Bitcoin toàn cầu. Điều thứ hai là tiếp tục giải quyết tất cả bài toán thiên niên kỷ khác. Lúc này, họ sẽ đưa nhân loại “tiến hoá” thêm một bậc.

Để hiểu tại sao lại như vậy, cần biết máy tính là thiết bị giải quyết vấn đề, trong đó thông tin được trừu tượng thành mã có thể đọc được bằng thiết bị vật lý, dựa trên các nguyên tắc do Alan Turing đưa ra. Giải quyết vấn đề cần một số bước và khoảng thời gian nhất định, lượng thời gian cần thiết sẽ tăng lên khi vấn đề ngày càng lớn.

Giai duoc bai toan nay, ban se co toan bo Bitcoin tren the gioi hinh anh 2
P so với NP được Stephen Cook đưa ra năm 1971 trong bài báo nổi tiếng "The complexity of theorem proving procedures". Ảnh: Kevin Van Paassen.

Từ việc đơn giản nhân hai số đến các tác vụ phức tạp hơn như dùng trình duyệt Internet, máy tính về cơ bản đang cố giải quyết các phép toán nhân chia cộng trừ.

Khi một vấn đề phát triển phức tạp, lượng thời gian cần thiết để giải quyết tăng lên trong thời gian đa thức. Đa thức là một số có lũy thừa và hệ số (ví dụ như n luỹ thừa 2). Nếu một vấn đề có thể giải quyết được trong thời gian n mũ 2, khi tăng gấp đôi kích thước của vấn đề (2n), lượng thời gian cần thiết để giải quyết sẽ tăng lên bốn lần (2n luỹ thừa 2).

Như vậy, các tác vụ trong máy tính đều có thể tính được sau bao lâu thì máy tính giải quyết xong vấn đề được đưa ra.

Giải quyết và kiểm chứng

Có rất nhiều vấn đề trong đó người ta có thể kiểm tra một câu trả lời là đúng trong thời gian đa thức (tính được thời gian kiểm tra đáp án), nhưng quá trình để được câu trả lời đó có thể không là thời gian đa thức (tức là có thể tìm thấy lời giải hoặc không tìm thấy lời giải trong một khoảng thời gian nào đó, không thể xác định chính xác sau bao lâu thì tìm được lời giải).

Đây được gọi là các vấn đề NP “Nondeterministic Polynomial time” - vấn đề không xác định thời gian đa thức.

Sudoku là một vấn đề NP khó giải quyết, dễ kiểm tra. Ví dụ quan trọng khác là tách một số thành các số nguyên tố. Hiện phải mất một thời gian rất lâu, chậm hơn thời gian đa thức để tách các số rất lớn thành các số nguyên tố. Tuy nhiên kiểm tra xem câu trả lời có đúng không chỉ đơn giản là nhân các số kết quả với nhau. Ý tưởng này là nền tảng của mã hóa hiện đại, dựa trên việc tạo các khóa bảo mật dễ xác minh nhưng khó bẻ khóa.

Giai duoc bai toan nay, ban se co toan bo Bitcoin tren the gioi hinh anh 3
Nếu chứng minh được P=NP, bạn sẽ làm lủng đoạn toàn bộ hệ thống bảo mật thế giới chứ không riêng Bitcoin. Ảnh: Cryptoline News.

Người ta từng nghĩ rằng máy tính lượng tử có thể giải quyết được các vấn đề NP khó nhất, được gọi là các vấn đề NP-đầy đủ. Nhưng không như kì vọng, máy tính lượng tử chỉ có thể giải quyết một số vấn đề P trong thời gian ngắn hơn (đa thức thấp hơn) hoặc chuyển một số vấn đề NP sang khái quát lượng tử của P, được gọi là BQP hoặc Thời gian đa thức lỗi Bounded-Error.

Do hiện tại người ta vẫn chưa chứng minh được P = NP, toàn bộ hệ thống mã hoá của chúng ta vẫn còn đảm bảo an ninh. Hacker phải mất nhiều thời gian để bẻ khoá hơn là thời gian tạo ra các khoá đó. Bitcoin cũng dựa trên nền tảng mã hoá này, do đó, nó vẫn còn là loại tiền tệ an toàn.

Nếu có thể tìm ra giải pháp hiệu quả cho những vấn đề NP-đầy đủ, bạn có thể tìm giải pháp hiệu quả cho tất cả các vấn đề NP. Điều này cho phép bạn giải quyết một loạt các vấn đề tối ưu hóa tương tự khác.

Nếu thành công trong việc chứng minh P bằng NP, bạn sẽ kiếm được ít nhất 1 triệu USD, thậm chí còn nhiều hơn thế nữa. Nếu không thành công cũng tốt, nó cho thấy các hệ thống mã hoá toàn cầu vẫn còn được đảm bảo an ninh.




Theo news.zing.vn

0 Bình luận
Game online - Phong Vũ - 29/05/2020 04:30
(infogame.vn) - Với việc Rogue Games quyết định rút lui, Vainglory trở lại Super Evil Mega Corp với tư cách là một phiên bản cộng đồng với nhiều tính năng bị giới hạn. 
Game online - Phong Vũ - 27/05/2020 05:00
(infogame.vn) - Hello Games cũng cho biết No Man's Sky sẽ có phiên bản PC tương thích Windows 10...
Game online - Phong Vũ - 27/05/2020 04:30
(infogame.vn) - NPH Funtap chính thức xác nhận thông tin sẽ cho ra mắt game nhập vai đánh theo lượt lấy chủ đề Naruto mang tên Hỏa Chí Anh Hùng trong thời gian tháng 6 tới đây.
Game online - Phong Vũ - 27/05/2020 01:00
(infogame.vn) - Đây là một game bắn súng khai thác bối cảnh vòng lặp thời gian, cho phép người chơi hợp tác cùng chính bản thân mình ở cả quá khứ và tương lai.
Game online - Phong Vũ - 26/05/2020 02:00
(infogame.vn) - Call of Duty: WWII gia tăng số lượng game miễn phí trong tháng 5 của PS Plus, hiện bao gồm Farming Simulator 19 và City: Skylines.
Game online - Phong Vũ - 25/05/2020 01:30
(infogame.vn) - Tuy nhiên theo đánh giá từ nhiều người chơi, Warzone đang đi lại con đường cũ của PUBG...
Game online - Phong Vũ - 22/05/2020 01:00
(infogame.vn) - Phiên bản toàn cầu này sẽ tiếp cận nhiều người chơi hơn trên toàn thế giới và cung cấp các tính năng, hỗ trợ chơi trò chơi được cải thiện bằng 14 ngôn ngữ...
Game online - Phong Vũ - 21/05/2020 04:00
(infogame.vn) - Trước đó, A: IR [Reverse] là tên dự kiến và đến hiện tại nhà phát triển đã lựa chọn Elyon là tên gọi chính thức của dự án này cho cả 2 phiên bản phát hành tại Hàn Quốc và Đông Nam Á.
GAME ONLINE - Phong Vũ - 29/05/2020 16:30
(infogame.vn) - Với việc Rogue Games quyết định rút lui, Vainglory trở lại Super Evil Mega Corp với tư cách là một phiên bản cộng đồng với nhiều tính năng bị giới hạn. 
GAME OFFLINE - Hữu Phong - 29/05/2020 16:00
(infogame.vn) - Kỷ niệm 30 năm phát hành, tạp chí danh tiếng Famitsu đã có cuộc khảo sát với các fan của dòng game 'Mộc đế' huyền thoại.
GAME MOBILE - Tiểu Vũ - 29/05/2020 15:00
(infogame.vn) - Theo đó, bản cập nhật sau 01 tháng ra mắt sẽ bao gồm tính năng mới - Kết hôn, mở các hoạt động Liên server, phái mới Độc Cô, tối ưu một số các tính năng khác để phù hợp hơn với thị hiếu của game thủ Việt.
CỘNG ĐỒNG 360 - T.X - 29/05/2020 15:00
(infogame.vn) - Mới đây, Jun Vũ đã khiến người hâm mộ không khỏi cảm thán khi đăng tải bộ hình thả dáng nóng bỏng cùng chiếc váy xuyên thấu vô cùng khéo léo.
GAME MOBILE - Phong Vũ - 29/05/2020 14:30
(infogame.vn) - Giai đoạn thử nghiệm chưa có dấu hiệu hạ nhiệt, Kiếm Hồn 3D lại tiếp tục công bố đại diện hình ảnh của dự án là “biểu tượng phái đẹp” Á hậu Huyền My, một tựa game đỉnh cao đi cùng một nhan sắc đậm chất Á đông tạo nên sự kết hợp “có một không hai”.
GAME MOBILE - Phong Vũ - 29/05/2020 14:00
(infogame.vn) - Hãy cùng gặp gỡ LọLemNhem và [LN]VoDanh sau khi cặp đôi này vượt qua nhiều đối thủ nặng kí, trở thành cặp đôi Song Vương Thiên Hạ mạnh nhất của Tru Tiên 3D.
CỘNG ĐỒNG 360 - T.X - 29/05/2020 12:30
(infogame.vn) - Cô bạn gái dùng dao rạch mạnh 1 đường giữa chiếc thùng, đường rạch đó lại vô tình vào trúng đầu chàng trai đang ngồi trong hộp.
GAME OFFLINE - - 29/05/2020 10:00
Trong các tựa game, một số phân cảnh tới rồi đi, nhưng những ký ức buồn thì thường đọng lại lâu.
GAME MOBILE - Tiểu Vũ - 29/05/2020 10:00
(infogame.vn) - Được cộng đồng game thủ biết tới dưới danh xưng “kiệt tác kiếm hiệp Kim Dung” và thu hút hàng triệu người chơi chỉ sau 3 tháng ra mắt, nhưng không vì thế mà Giang Hồ Chi Mộng “ngủ quên trên chiến thắng”. Mới đây, tựa game này đã đầu tư sản xuất 1 clip ngắn vô cùng ý nghĩa để gửi lời nhắn nhủ tới những game thủ thân thương: “Vượt giới hạn - Đạt ước mơ!”
CỘNG ĐỒNG 360 - T.X - 28/05/2020 21:00
(infogame.vn) - Lần đầu công khai thể hiện tình cảm trên mạng xã hội, cặp đôi Bomman và Minh Nghi bất ngờ nhận bão like từ người hâm mộ.
GAME MOBILE - Tiểu Vũ - 28/05/2020 18:00
(infogame.vn) - Liên tục tung các bản update với nhiều tính năng mới và sự kiện hấp dẫn, AxE là một trong số ít các tựa game rất biết cách chiều lòng anh em game thủ.
GAME MOBILE - T.X - 28/05/2020 18:00
(infogame.vn) - Bước sang tháng 6, NPH game Việt hứa hẹn sẽ đưa đến cho người chơi nhiều tựa game thu hút, hấp dẫn.
GIFT CODE - Phong Vũ - 28/05/2020 17:00
(infogame.vn) - Không phải chờ đợi lâu hơn nữa, ngay bây giờ, bạn đã có thể tải ngay Loạn Thế Anh Hùng 3Q từ CH Play hoặc App Store và thử sức với gameplay chiến thuật siêu “hack não”.
PHIM MANGA - Khánh Ly - 28/05/2020 16:00
(infogame.vn) - Một kỷ lục vô tiền khoáng hậu được lập ra bởi Demon Slayer: Kimetsu no Yaiba.
GAME MOBILE - Phong Vũ - 28/05/2020 14:00
(infogame.vn) - Trong bản cập nhật ngày 29/5 này, game thủ Tân Thần Điêu VNG sẽ được trải nghiệm 7 hoạt động Liên server, hứa hẹn “đốt cháy” làng game trong những ngày tháng 6/2020.
Xem thêm