Locally Testable Proofs: The PVP Problem
/ 7 min read
This work is supported by a grant from the Mina Foundation
In his book “Introduction to Property Testing” Oded Goldreich provides a wonderful proof of the how to construct a Probabilistically Checkable Proof(PCP) for NP-complete problems1. This proof uses the partially vanishing polynomial problem(PVPP) as an example of an NP-complete type problem. In this post we walkthrough Prof. Goldreich’s proof with the goal of build intuition around PCPs and local testing.
In computational complexity theory, Probabilistically Checkable Proofs (PCPs) are a powerful tool that allows a verifier to check the correctness of a proof by examining only a small portion of it. This method leverages randomness and the properties of polynomials over finite fields to efficiently verify complex statements with high confidence. In this blog post, we explore how to construct a PCP to verify that a given polynomial satisfies a specific equation, using auxiliary polynomials to facilitate the verification process.
Introduction to the Partially Vanishing Polynomial Problem
The Partially Vanishing Polynomial Problem (PVPP) involves verifying whether a given multivariate polynomial satisfies a specific vanishing condition when composed with another polynomial over a finite field . Specifically, the goal is to check if:
holds for all and , where is a subset (often a subfield or small subset) of .
The challenge lies in verifying this condition efficiently, even though directly checking it would require evaluating the polynomial at an exponential number of points. The solution involves constructing a PCP over a large alphabet, enabling the verifier to check the condition by making a small number of queries to a proof oracle. This proof was first described “Proof Verification and Hardness of Approximation Problems”2 paper.
Problem Setup
The proof involves the following components:
-
Main Polynomial : An -variate polynomial of total degree at most , which is supposed to satisfy the vanishing condition with .
-
Auxiliary Polynomials : A sequence of polynomials for . Each is supposed to have total degree .
-
Vanishing Conditions: The auxiliary polynomials are designed to assist in verifying that on , where:
The core idea is to use a sequence of polynomials that progressively “extend” the vanishing property from a small subset to the entire domain, leveraging low-degree extensions and consistency checks.
We can think of the auxiliary polynomials as conceptually close to the terms sent by the prover in the sumcheck protocol. And they serve a similiar purpose, with each auxiliary polynomial reducing the size of the previous problem.
Constructing the PCP
The prover first builds a proof and sends it to the verifier. This proof is made up of the following components.
1. Constructing the Polynomials
-
Main Polynomial :
-
is an -variate polynomial with total degree at most .
-
The goal is to verify that satisfies the vanishing condition with on .
-
Note: is the statement we are trying to prove.
-
-
Auxiliary Polynomials :
-
For , define polynomials .
-
Each is supposed to vanish on the set , which means:
-
The degrees of are bounded by .
-
2. Purpose of the Auxiliary Polynomials
- The auxiliary polynomials help in extending the vanishing condition from a small subset to the entire space .
- By ensuring that vanishes on and that and agree on certain lines, we can inductively show that vanishes on .
Verifier Protocol
The verification process involves the following steps:
Step 1: Testing that is a Low-Degree Polynomial
-
Objective: Verify that has total degree at most .
-
Method: Perform a Low-Degree Test on :
-
Randomly select a line in . A line is defined as:
where , and .
-
Restrict to to obtain a univariate polynomial .
-
Check whether has degree at most .
-
-
Reasoning: If is of low total degree, then its restriction to any line is a low-degree univariate polynomial.
Step 2: Testing that Each is of Low Degree
-
Objective: Verify that each has total degree at most .
-
Method: For each :
- Randomly select a line in .
- Restrict to to obtain .
- Check whether has degree at most .
Step 3: Testing Consistency Between and
-
Objective: Verify that and agree on .
-
Method:
-
For each :
-
Randomly select:
-
Evaluate:
-
Consistency Check: Accept if .
-
-
-
Additional Low-Degree Test:
-
Restrict to the axis-parallel line:
-
Check that is a univariate polynomial of degree at most .
-
-
Reasoning:
- Ensuring that and agree on helps propagate the vanishing property from to .
- By induction, if vanishes on and the polynomials are consistent, then vanishes on .
Step 4: Testing that Vanishes on
-
Objective: Verify that for all .
-
Method:
- Randomly select .
- Evaluate .
- Zero Test: Accept if .
-
Reasoning:
- Since , this shows that satisfies the vanishing condition when composed with .
As you can see from the verification steps listed above, the process of build a PCP verifier for an NP-Complete problem is highly non-trivial and requires several complex steps. The key to understanding this proof is understanding the recursive structure of the degree reduction between each polynomial. Fundametally the goal of this PCP is to reduce a large problem, to a very small problem and prove that the small problem directlty ties back to the large problem.
Inductive Argument
The verification process relies on the following inductive reasoning:
- Base Case: vanishes on by direct testing.
- Inductive Step: If vanishes on and agrees with on , then vanishes on .
By induction, vanishes on , which is the desired property. Since , this shows that satisfies the vanishing condition when composed with .
Query Complexity
-
Oracle Length:
-
The oracle (proof) includes:
- The evaluations of over : entries.
- The evaluations of each over : entries.
-
Total Length:
-
-
Query Complexity:
-
The verifier makes queries when performing:
- Low-degree tests on and each .
- Consistency checks between and .
- Zero tests on .
-
Total Queries:
- Each low-degree test involves querying points along random lines, typically points per line.
- The number of lines tested is per polynomial.
- For polynomials, the total queries are .
- The consistency checks involve querying and at random points, adding more queries.
-
Total Query Complexity:
-
Conclusion
By constructing auxiliary polynomials and leveraging probabilistic verification techniques, we can efficiently verify complex polynomial equations within a PCP framework. This approach reduces the verification of global properties to local checks, enabling the verifier to detect inconsistencies with high probability while examining only a small portion of the proof.
Footnotes
-
O. Goldreich, Introduction to Property Testing. Cambridge: Cambridge University Press, 2017. ↩
-
S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. Proof Verification and Intractability of Approximation Problems. Journal of the ACM, Vol. 45, pages 501–555, 1998. Preliminary version in 33rd FOCS, 1992. ↩