Tính toán ngẫu nhiên và tương tác

Việc cho phép các thuật toán tung đồng xu hoặc tham gia vào một cuộc đối thoại với một người chứng minh mạnh mẽ nhưng không đáng tin cậy đã tạo ra các lớp phức tạp như BPP và IP, định hình lại sự hiểu biết của chúng ta về những gì xác minh hiệu quả có thể đạt được.

Definition

Tính toán ngẫu nhiên bổ sung cho một máy khả năng truy cập vào các bit ngẫu nhiên và đo lường xác suất của một câu trả lời đúng, trong khi tính toán tương tác cho phép một trình xác minh thời gian đa thức trao đổi thông điệp với một người chứng minh; các lớp kết quả nắm bắt các vấn đề có thể giải quyết được với lỗi giới hạn hoặc có thể xác minh thông qua tương tác.

Scope

Chủ đề này bao gồm các lớp phức tạp xác suất như BPP, RP và ZPP và câu hỏi liệu tính ngẫu nhiên có thể được loại bỏ hay không, các hệ thống chứng minh tương tác và định lý xác định IP với PSPACE, các chứng minh không kiến thức, và các chứng minh có thể kiểm tra xác suất làm nền tảng cho độ khó của xấp xỉ.

Core questions

• Liệu việc truy cập vào tính ngẫu nhiên có cho phép các thuật toán giải quyết nhiều vấn đề hiệu quả hơn không?
• Liệu một trình xác minh hạn chế có thể kiểm tra các tuyên bố được đưa ra bởi một người chứng minh mạnh mẽ, không đáng tin cậy không?
• Làm thế nào để một người có thể tin rằng một tuyên bố là đúng mà không học được bất cứ điều gì khác?
• Việc kiểm tra chứng minh tương tác và xác suất hạn chế sự xấp xỉ như thế nào?

Key theories

IP bằng PSPACE

Các ngôn ngữ có thể chứng minh được bằng một giao thức tương tác giữa một trình xác minh thời gian đa thức và một người chứng minh toàn năng chính xác là những ngôn ngữ có thể quyết định được trong không gian đa thức, một thước đo nổi bật về sức mạnh của tương tác.

Định lý PCP

Mọi vấn đề trong NP đều có các chứng minh có thể được xác minh bằng cách đọc chỉ một số lượng bit được chọn ngẫu nhiên không đổi, một kết quả xác định ngưỡng chính xác mà vượt qua đó việc xấp xỉ nhiều vấn đề tối ưu hóa là NP-khó.

Clinical relevance

Những ý tưởng này có tác động công nghệ trực tiếp: các chứng minh không kiến thức cho phép xác thực và các giao thức bảo vệ quyền riêng tư, đồng thời củng cố tính toán có thể xác minh trong chuỗi khối (blockchains), trong khi các chứng minh có thể kiểm tra xác suất giải thích tại sao nhiều vấn đề tối ưu hóa không thể được xấp xỉ một cách hiệu quả, hướng dẫn nơi các thuật toán xấp xỉ có thể và không thể thành công.

History

Các chứng minh tương tác và không kiến thức được Goldwasser, Micali và Rackoff cùng với Babai giới thiệu vào giữa những năm 1980. Shamir đã chứng minh IP bằng PSPACE vào năm 1990, và định lý PCP, được Arora và những người khác hoàn thành vào đầu những năm 1990, đã cách mạng hóa việc nghiên cứu xấp xỉ, trong khi giả thuyết đang tồn tại rằng thời gian đa thức ngẫu nhiên bằng thời gian đa thức xác định vẫn còn bỏ ngỏ.

Debates

Liệu tính ngẫu nhiên có bổ sung sức mạnh tính toán thực sự không?

Nhiều kết quả cho thấy BPP bằng P dưới các giả định độ khó hợp lý, nghĩa là tính ngẫu nhiên về nguyên tắc có thể được loại bỏ khỏi các thuật toán hiệu quả. Việc khử ngẫu nhiên này có đúng vô điều kiện hay không vẫn chưa được giải quyết, để ngỏ câu hỏi về mức độ thiết yếu của tính ngẫu nhiên.

Key figures

• Shafi Goldwasser
• Silvio Micali
• László Babai
• Adi Shamir

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

Làm thế nào việc tung đồng xu có thể giúp một thuật toán?

Tính ngẫu nhiên cho phép một thuật toán tránh các đầu vào trường hợp xấu nhất bằng cách đưa ra các lựa chọn mà đối thủ không thể dự đoán, thường mang lại các quy trình đơn giản hơn hoặc nhanh hơn, như trong kiểm tra tính nguyên tố. Lớp lỗi giới hạn BPP nắm bắt các vấn đề có thể giải quyết theo cách này với một xác suất lỗi nhỏ, có thể kiểm soát được.

Chứng minh không kiến thức là gì?

Đó là một giao thức tương tác thuyết phục một trình xác minh rằng một tuyên bố là đúng trong khi không tiết lộ bất cứ điều gì ngoài sự thật của nó, thậm chí cả lý do tại sao nó đúng. Các chứng minh như vậy cho phép, ví dụ, chứng minh bạn biết mật khẩu hoặc bí mật mà không tiết lộ nó, và chúng là nền tảng cho quyền riêng tư mật mã hiện đại.