Tham gia Đăng nhập
Điểm:0
avatar Crypto

Chứng minh đầu ra của một chức năng chung

lá cờ ma
Matteo Monti

Có bất kỳ cấu trúc chung nào để chứng minh tính đúng đắn của đầu ra của hàm không? Nói cách khác, có một cách chung để tạo ra một bằng chứng cho tuyên bố $y = f(x)$?

Chính thức hơn, hãy để $f: X \rightarrow Y$ là một chức năng chung. Được cho $f$, có cách chung nào để xây dựng chức năng tạo nhân chứng không $p: X \rightarrow W$ và một đề xuất $V(x, y, w)$ như vậy, cho tất cả $x$, chỉ có $V(x, f(x), p(x))$ là đúng, và xác minh $V(x, y, w)$ nhanh hơn máy tính $f(x)$?

36
0 + 0
Maarten Bodewes avatar
lá cờ in
Maarten Bodewes
Không phải chức năng một chiều bác bỏ điều này?
0
Hồi đáp
poncho avatar
lá cờ my
poncho
Một hàm có thể là một phản ví dụ là hàm $f(x)=0$ (với mọi $x$); vâng, thật dễ dàng để xây dựng một đề xuất cho $f$ này; Tôi không biết liệu bạn có thể xây dựng một cái chạy **nhanh hơn** so với tính toán $f$...
2
Hồi đáp
lá cờ ma
Matteo Monti
@poncho tôi đoán đó là một điểm khá công bằng.
0
Hồi đáp
Wilson avatar
lá cờ se
Wilson
Để làm rõ, nếu tôi đang đọc chính xác. Bạn đang tự hỏi liệu có tồn tại một thuật toán xác minh hiệu quả và bằng chứng ngắn gọn (trong thời gian ít hơn so với đánh giá hàm) để kiểm tra xem f, x và y công khai có y=f(x) hay không?
0
Hồi đáp
lá cờ ma
Matteo Monti
@Wilson chính xác! Tôi biết nó tồn tại đối với một số chức năng (ví dụ: các chức năng một chiều có thể sử dụng đầu ra của chúng làm nhân chứng), vì vậy tôi tự hỏi liệu có tồn tại một số cơ chế tổng quát hơn không!
0
Hồi đáp
Wilson avatar
lá cờ se
Wilson
Hãy xem xét một hàm chung f được biểu diễn bằng một tập hợp các mạch số học, vấn đề này có được giải quyết bằng cách xử lý trước SNARK không? Độ phức tạp thời gian của trình xác minh là đa logarit trong độ phức tạp của mạch. Ngoài ra còn có một dòng tài liệu gọi là tính toán có thể kiểm chứng có thể cũng là thứ bạn đang tìm kiếm.
0
Hồi đáp
Wilson avatar
lá cờ se
Wilson
Hãy lấy ví dụ ngược của poncho trong ngữ cảnh. $f(x)=0$ là một hàm có thể tính toán được trong thời gian không đổi. Do đó, các yếu tố không đổi trong thuật toán xác minh sẽ lớn hơn độ phức tạp logarit, nhưng đối với các hàm không tầm thường, phương pháp này sẽ đánh bại việc đánh giá hàm.
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.