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ũ - 17/11/2019 01:00
(infogame.vn) - Cả cốt truyện cũ và mới sẽ dẫn đến cùng một bản kết thúc của Atlas và phần tiếp theo giữ lại tất cả nội dung mở rộng đã được tạo ra trong sáu năm qua.
Game online - Phong Vũ - 16/11/2019 01:00
(infogame.vn) - Phát hành lần đầu tiên vào năm 2004, KartRider, đã thu hút được 300 triệu người chơi ở châu Á và trở thành một hiện tượng esports tại Hàn Quốc.
Game online - Phong Vũ - 15/11/2019 03:00
(infogame.vn) - Trước đó, Project K được lựa chọn là tên gọi ban đầu của dự án và đã thay đổi thành Plan 8 ở thời điểm hiện tại. Dự án này được dẫn dắt bởi Lee Seung-gi, giám đốc thiết kế thế giới cho Black Desert và Black Desert Mobile kể từ những ngày đầu của Pearl Abyss.
Game online - T.X - 14/11/2019 03:00
(infogame.vn) - Vào lúc 20h00 ngày hôm nay 14/11, đội tuyển Việt Nam sẽ có trận đấu trên sân Mỹ Đình gặp đội tuyển UAE trong vòng loại World Cup 2022 khu vực châu Á.
Game online - Theo Trí Thức Trẻ - 13/11/2019 08:47
Thay vì nhảy dù trong PUBG thì bạn có thể tiết kiệm tiền đi du lịch tới các địa điểm này.
Game online - Theo Zing.vn - 11/11/2019 09:24
Hack cheat tràn lan, streamer nổi tiếng từ bỏ, người chơi phổ thông cũng đang dần nói không với PUBG để chuyển sang tựa game khác thú vị hơn.
Game online - Theo Download.com.vn - 11/11/2019 09:07
Liên quân Mobile là một trong những tựa game hot nhất hiện nay. Dù chỉ ra đời với phiên bản dành cho hệ điều hành di động, nhưng nếu muốn, chúng ta vẫn có thể chơi Liên quân Mobile bằng máy tính thông qua các giả lập Android phổ biến hiện nay.
Game online - Theo Download.com.vn - 11/11/2019 09:04
Chơi Đột Kích thế nào? Hay làm cách nào để trở thành tay súng huyền thoại trong Đột Kích? Đó là câu hỏi mà không ít người đặt ra khi tham gia vào tựa game này. Vậy câu trả lời là gì? Người chơi phải làm sao mới có thể trở thành "thiện xạ" trong Đột Kích (Cross Fire)?
GAME ONLINE - Phong Vũ - 17/11/2019 13:00
(infogame.vn) - Cả cốt truyện cũ và mới sẽ dẫn đến cùng một bản kết thúc của Atlas và phần tiếp theo giữ lại tất cả nội dung mở rộng đã được tạo ra trong sáu năm qua.
CÔNG NGHỆ - - 17/11/2019 12:30
Với khối tài sản lên tới 110 tỷ USD, tỷ phú Bill Gates sở hữu nhiều siêu xe và bất động sản xa hoa.
ESPORTS - - 17/11/2019 11:30
Vậy là sau quãng thời gian chờ đợi gần 2 tuần, fan của 1977 Vlog lại sắp được đón thêm một "siêu phẩm" để thỏa lòng ước mong...
ESPORTS - - 17/11/2019 11:30
Hot girl triệu triệu người like đây rồi. Chân lý cuộc đời là đây chứ đâu.
ESPORTS - Phong Vũ - 17/11/2019 11:00
Lưu ý là Doinb là một Streamer rất nổi tiếng và anh chàng này không thiếu cách để pha trò cho người hâm mộ nên đừng tin 100% vào những gì được kể.
CỘNG ĐỒNG 360 - T.X - 17/11/2019 09:00
(infogame.vn) - NTN - Nguyễn Thành Nam mới đây đăng đoạn clip với dòng tiêu đề gây sốc "Xóa kênh".
CÔNG NGHỆ - - 16/11/2019 15:47
Bên cạnh một số cái tên như Instagram, Facebook hay Twitter, Flappy Bird cũng được Cnet bình chọn là một trong những ứng dụng quan trọng nhất hơn 10 năm vừa qua.
PHIM MANGA - Khánh Ly - 16/11/2019 15:00
(infogame.vn) - Thêm một chap hồi tưởng nữa về cuộc đời Oden trong One Piece.
GAME ONLINE - Phong Vũ - 16/11/2019 13:00
(infogame.vn) - Phát hành lần đầu tiên vào năm 2004, KartRider, đã thu hút được 300 triệu người chơi ở châu Á và trở thành một hiện tượng esports tại Hàn Quốc.
GAME MOBILE - Tiểu Vũ - 16/11/2019 13:00
(infogame.vn) - Game thủ ngày càng có lý do để tin rằng Tần Mỹ Nhân là một trong những tựa game sở hữu nền tảng đồ họa 3D siêu thực.
CÔNG NGHỆ - P.V - 16/11/2019 12:38
(infogame.vn) - Đây là các ứng dụng không có gì đặc biệt nhưng được bán với giá lên tới 9 triệu đồng trên cửa hàng trực tuyến Google Play, điều đặc biệt mỗi ứng dụng này có trung bình hơn 50 lượt tải, ước tính thu về gần 39 tỉ đồng.
ESPORTS - Phong Vũ - 16/11/2019 11:00
Potm sẽ là sự bổ sung rất chất lượng cho FTV
CỘNG ĐỒNG - Phong Vũ - 16/11/2019 09:00
Bất ngờ lớn nhất mà FIFA Online 4 hứa hẹn sẽ đem đến cho game thủ trong bản Roster Update đang dần được hé lộ, và trái với dự đoán của tất cả mọi người, đó chính là sự xuất hiện của các cầu thủ Việt Nam.
CỘNG ĐỒNG 360 - T.X - 15/11/2019 22:00
(infogame.vn) - Vậy là hai đội tuyển Liên Quân Mobile đến từ Việt Nam sẽ gặp nhau ở trận Bán kết AIC 2019 sắp tới.
CỘNG ĐỒNG 360 - T.X - 15/11/2019 21:00
(infogame.vn) - NTN lại tiếp tục khiến dân mạng một lần nữa dậy sóng.
Xem thêm