Проверочные доказательства с вероятностью: теория и применение.
Probabilistically checkable proof
Доказательства с вероятностной проверкой (PCP) в теории сложности: проверка доказательств рандомизированным алгоритмом с малым объемом чтения. Классы сложности.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В теории вычислительной сложности вероятностно проверяемое доказательство (PCP) — это тип доказательства, которое может быть проверено рандомизированным алгоритмом, использующим ограниченное количество случайности и считывающим ограниченное число битов доказательства. Алгоритм должен принимать корректные доказательства и отклонять некорректные доказательства с очень высокой вероятностью. Стандартное доказательство (или сертификат), используемое в определении класса сложности NP на основе верификатора, также удовлетворяет этим требованиям, поскольку процедура проверки детерминированно читает всё доказательство, всегда принимает корректные доказательства и отклоняет некорректные доказательства. Однако, интересным их делает существование вероятностно проверяемых доказательств, которые можно проверить, прочитав лишь несколько битов доказательства, используя случайность принципиальным образом. Вероятностно проверяемые доказательства порождают множество классов сложности в зависимости от количества запросов и объёма используемой случайности. Класс PCP[r(n),q(n)] относится к множеству задач принятия решений, для которых существуют вероятностно проверяемые доказательства, которые могут быть проверены за полиномиальное время, используя не более r(n) случайных битов и считывая не более q(n) битов доказательства. Если не указано иное, корректные доказательства всегда должны приниматься, а некорректные доказательства должны отклоняться с вероятностью, превышающей 1/2. Теорема о PCP, являющаяся ключевым результатом в теории вычислительной сложности, утверждает, что PCP[O(log n),O(1)] = NP.
In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate), as used in the verifier based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way. Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The class PCP[r(n),q(n)] refers to the set of decision problems that have probabilistically checkable proofs that can be verified in polynomial time using at most r(n) random bits and by reading at most q(n) bits of the proof. Unless specified otherwise, correct proofs should always be accepted, and incorrect proofs should be rejected with probability greater than 1/2. The PCP theorem, a major result in computational complexity theory, states that PCP[O(log n),O(1)] = NP.
История и значение
Теория вероятностно проверяемых доказательств изучает возможности вероятностно проверяемых систем доказательств при различных ограничениях параметров (полнота, надёжность, сложность случайности, сложность запросов и размер алфавита). Она находит применение в вычислительной сложности (в частности, в задаче об оценке сложности приближённого решения) и криптографии. Определение вероятностно проверяемого доказательства было явно введено Аророй и Сафрой в 1992 году, хотя свойства, связанные с ними, изучались и ранее. В 1990 году Бабаи, Фортноу и Лунд доказали, что PCP[poly(n), poly(n)] = NEXP, установив первое нетривиальное соответствие между стандартными доказательствами (NEXP) и вероятностно проверяемыми доказательствами. Теорема о вероятностно проверяемых доказательствах, доказанная в 1992 году, утверждает, что PCP[O(log n),O(1)] = NP. Теория сложности приближённых вычислений требует глубокого понимания роли полноты, надёжности, размера алфавита и сложности запросов в вероятностно проверяемых доказательствах.
The theory of probabilistically checkable proofs studies the power of probabilistically checkable proof systems under various restrictions of the parameters (completeness, soundness, randomness complexity, query complexity, and alphabet size). It has applications to computational complexity (in particular hardness of approximation) and cryptography. The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992, although their properties were studied earlier. In 1990 Babai, Fortnow, and Lund proved that PCP[poly(n), poly(n)] = NEXP, providing the first nontrivial equivalence between standard proofs (NEXP) and probabilistically checkable proofs. The PCP theorem proved in 1992 states that PCP[O(log n),O(1)] = NP. The theory of hardness of approximation requires a detailed understanding of the role of completeness, soundness, alphabet size, and query complexity in probabilistically checkable proofs.
Линейный ПЦП
Линейный PCP — это PCP, в котором доказательство представляет собой вектор элементов конечного поля, и оракул PCP может выполнять только линейные операции над доказательством. В частности, ответ оракула на запрос верификатора является линейной функцией. Линейные PCP имеют важное применение в доказательных системах, которые могут быть скомпилированы в SNARK.
A Linear PCP is a PCP in which the proof is a vector of elements of a finite field , and such that the PCP oracle is only allowed to do linear operations on the proof. Namely, the response from the oracle to a verifier query is a linear function Linear PCPs have important applications in proof systems that can be compiled into SNARKs.