Chứng minh có thể kiểm chứng ngẫu nhiên (độ phức tạp)

Trong lý thuyết độ phức tạp tính toán, chứng minh có thể kiểm chứng ngẫu nhiên (PCP - viết tắt của probabilistically checkable proof) là một chứng minh có thể được kiểm tra bởi một thuật toán ngẫu nhiên sử dụng một số lượng nhỏ bit ngẫu nhiên và một số lượng nhỏ bit của chứng minh. Thuật toán sau đó phải chấp nhận chứng minh đúng và từ chối chứng minh sai với xác suất cao. Chứng minh sử dụng trong định nghĩa dựa trên thuật toán kiểm chứng của NP cũng thỏa mãn 2 yêu cầu này, bởi thuật toán kiểm chứng đọc toàn bộ chứng minh một cách tất định và chấp nhận chứng minh đúng, từ chối chứng minh sai. Tuy nhiên, điều thú vị ở đây là sự tồn tại của chứng minh có thể kiểm chứng được bằng cách chỉ đọc một vài bit của chứng minh cùng với việc sử dụng bit ngẫu nhiên một cách khôn ngoan.

Chứng minh có thể kiểm chứng ngẫu nhiên tạo ra nhiều lớp độ phức tạp tính toán khác nhau, phụ thuộc vào số lượng bit cần đọc của chứng minh, và số lượng bit ngẫu nhiên cần sử dụng. Lớp PCP$(r(n),q(n))$ là tập hợp các bài toán quyết định có chứng minh có thể kiểm chứng ngẫu nhiên sử dụng tối đa $r(n)$ bit ngẫu nhiên và đọc tối đa $q(n)$ bit của chứng minh. Thông thường, chứng minh đúng luôn được chấp nhận và chứng minh sai bị từ chối với xác suất ít nhất 1/2. Định lý PCP chứng minh rằng PCP$(O(\log n),O(1))=$NP.

Định nghĩa

Một Hệ thống kiểm chứng ngẫu nhiên với tham số toàn vẹn c(n), tham số đúng đắn s(n), bảng chữ cái Σ, cho bài toán quyết định L, với $0\leq s(n)<c(n)\leq 1$ là một máy Turing ngẫu nhiên sử dụng máy tiên tri, tạm gọi là V, sao cho với dữ liệu vào x, và chứng minh $\pi \in \Sigma ^{*}$ đọc thông qua máy tiên tri,

• Điều kiện toàn vẹn: Nếu $x\in L$ thì tồn tại π sao cho $V^{\pi }(x)=1$ với xác suất ít nhất c(n).
• Điều kiện đúng đắn: Nếu $x\not \in L$ thì với mọi π’, $V^{\pi }(x)=1$ với xác suất tối đa s(n).

Hai tham số quan trọng khác của hệ thống là số lượng tối đa bit ngẫu nhiên r(n) và số lượng tối đa bit của chứng minh q(n) mà máy V sử dụng khi xử lý dữ liệu vào có độ dài n.

Hệ thống kiểm chứng là không thích ứng nếu V đưa ra vị trí tất cả các bit cần đọc từ chứng minh trước khi nhận được bất kì một bit nào.

Lịch sử và tầm quan trọng

Lý thuyết về chứng minh có thể kiểm chứng ngẫu nhiên nghiên cứu về khả năng của hệ thống kiểm chứng ngẫu nhiên với các giá trị tham số khác nhau (tham số toàn vẹn, tham số đúng đắn, số bit ngẫu nhiên, số bit của chứng minh, kích thước bảng chữ cái). Lý thuyết này có nhiều ứng dụng trong lý thuyết độ phức tạp tính toán (đặc biệt là chứng minh sự không xấp xỉ được), và mật mã học.

Định nghĩa của chứng minh có thể kiểm chứng ngẫu nhiên được đưa ra bởi Arora và Safra năm 1992, tuy nhiên các tính chất của chúng đã được nghiên cứu từ trước. Năm 1990, Babai, Fortnow, và Lund đã chứng minh PCP$(poly(n),poly(n))=$NEXP, đưa ra sự tương đương đầu tiên giữa chứng minh thông thường (NEXP) và chứng minh có thể kiểm chứng ngẫu nhiên. Định lý PCP năm 1992 chứng minh rằng PCP$O(\log n),O(1))=$NP.