Hậu quả của P=NP cho Xác thực

Hãy giả sử rằng P=NP. Nghĩa là, mọi vấn đề mà giải pháp có thể được xác minh nhanh chóng cũng có thể được giải quyết nhanh chóng, bất kể điều đó có nghĩa là gì ở cấp độ chính thức. Vì vậy, không chỉ làm P=NP, nhưng có các thuật toán thời gian đa thức thực tế cho NP-hoàn thành bài toán. Ngoài ra, bằng chứng là mang tính xây dựng hoặc không mang tính xây dựng. Nghĩa là, một thuật toán có thể được tìm thấy mà cuối cùng chúng ta sẽ tìm thấy đủ nhanh để bắt đầu sử dụng, ngay cả khi chúng ta không thể chứng minh được thuật toán đó. Sau đó, việc giữ bí mật trở nên khó khăn hơn nhiều - một vấn đề lớn. Điều khiến tôi sợ hãi không phải là chúng ta không có khả năng che giấu thông tin mà là không có khả năng tiết lộ thông tin đó.

Trong một xã hội phức tạp, chúng ta cần tin tưởng người khác và những gì chúng ta có thể xác minh độc lập là không đủ. Trên thực tế, chúng tôi thiết lập lòng tin với các tổ chức khi họ liên tục cung cấp cho chúng tôi thông tin chính xác. Tôi không thấy một phương pháp thay thế nào, vì vậy nếu chúng tôi mất khả năng xác minh rằng chúng tôi đang nhận thông tin từ một tổ chức cụ thể, thì kẻ mạo danh có thể khai thác lòng tin của chúng tôi, điều này không được phép. Do đó, chúng ta không thể có đầy đủ thông tin để có một xã hội phức tạp. P=NP sẽ phá hủy xác thực hiện tại và do đó gây ra rủi ro cơ bản nếu không tìm thấy các giải pháp khác.

Các giải pháp khác có thể được tìm thấy? Nếu P=NP, chúng ta có một thế giới không có quyền riêng tư, nhưng, để giảm thiểu thiệt hại về vấn đề đó, chúng ta có thể cố gắng xây dựng tính xác thực xung quanh thực tế đó. Thay vì các thực thể cung cấp cho chúng tôi thông tin chúng tôi cần để xác định chúng, chúng tôi chỉ có thể vắt kiệt thông tin đó từ chúng. Một ý tưởng là khi nhận được một tin nhắn, chúng tôi sẽ gửi tin nhắn của mình có chứa một số thông tin sẽ được gửi lại cho chúng tôi cùng với tin nhắn gốc, vì vậy chúng tôi sẽ biết rằng tin nhắn của chúng tôi đã được nhận và ít nhất người nhận muốn gửi tin nhắn gốc. thông điệp. Thông điệp của chúng tôi là phần mềm gián điệp, được tăng cường bởi thuật toán hiệu quả của chúng tôi để NP-hoàn thành các vấn đề mà chúng tôi sử dụng để xác minh nguồn gốc của thông báo.