skip to content
PSYCHO VIRTUAL

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 PP satisfies a specific vanishing condition when composed with another polynomial AA over a finite field F\mathbb{F}. Specifically, the goal is to check if:

P(x,z,y,τ,A(x),A(y),A(z))=0P\big(x, z, y, \tau, A(x), A(y), A(z)\big) = 0

holds for all x,y,zHmx, y, z \in H^m and τ{0,1}3H\tau \in \{0,1\}^3 \subset H, where HH is a subset (often a subfield or small subset) of F\mathbb{F}.

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:

  1. Main Polynomial AA: An mm-variate polynomial A:FmFA: \mathbb{F}^m \to \mathbb{F} of total degree at most mHm|H|, which is supposed to satisfy the vanishing condition with PP.

  2. Auxiliary Polynomials AiA_i: A sequence of 3m+13m + 1 polynomials Ai:F3m+1FA_i: \mathbb{F}^{3m+1} \to \mathbb{F} for i=1,,3m+1i = 1, \dots, 3m+1. Each AiA_i is supposed to have total degree d=(3mH+O(1))mHd = (3m|H| + O(1)) \cdot m|H|.

  3. Vanishing Conditions: The auxiliary polynomials are designed to assist in verifying that A0(x,y,z,τ)=0A_0(x, y, z, \tau) = 0 on H3m+1H^{3m+1}, where:

    A0(x,y,z,τ)=defP(x,z,y,τ,A(x),A(y),A(z))A_0(x, y, z, \tau) \stackrel{\text{def}}{=} P\big(x, z, y, \tau, A(x), A(y), A(z)\big)

The core idea is to use a sequence of polynomials AiA_i 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 AiA_i 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 π\pi and sends it to the verifier. This proof is made up of the following components.

1. Constructing the Polynomials

  • Main Polynomial AA:

    • AA is an mm-variate polynomial A:FmFA: \mathbb{F}^m \to \mathbb{F} with total degree at most mHm|H|.

    • The goal is to verify that AA satisfies the vanishing condition with PP on H3m+1H^{3m+1}.

    • Note: AA is the statement we are trying to prove.

  • Auxiliary Polynomials AiA_i:

    • For i=0,1,,3m+1i = 0, 1, \dots, 3m+1, define polynomials Ai:F3m+1FA_i: \mathbb{F}^{3m+1} \to \mathbb{F}.

    • Each AiA_i is supposed to vanish on the set FiH3m+1i\mathbb{F}^i H^{3m+1 - i}, which means:

      Ai(u,v)=0for all uFi,vH3m+1iA_i(u, v) = 0 \quad \text{for all } u \in \mathbb{F}^i, v \in H^{3m+1 - i}
    • The degrees of AiA_i are bounded by d=(3mH+O(1))mHd = (3m|H| + O(1)) \cdot m|H|.

2. Purpose of the Auxiliary Polynomials

  • The auxiliary polynomials help in extending the vanishing condition from a small subset H3m+1H^{3m+1} to the entire space F3m+1\mathbb{F}^{3m+1}.
  • By ensuring that AiA_i vanishes on FiH3m+1i\mathbb{F}^i H^{3m+1 - i} and that AiA_i and Ai1A_{i-1} agree on certain lines, we can inductively show that A0A_0 vanishes on H3m+1H^{3m+1}.

Verifier Protocol

The verification process involves the following steps:


Step 1: Testing that AA is a Low-Degree Polynomial

  • Objective: Verify that AA has total degree at most mHm|H|.

  • Method: Perform a Low-Degree Test on AA:

    • Randomly select a line LL in Fm\mathbb{F}^m. A line is defined as:

      L={a+bttF}L = \{ a + b t \mid t \in \mathbb{F} \}

      where a,bFma, b \in \mathbb{F}^m, and b0b \neq 0.

    • Restrict AA to LL to obtain a univariate polynomial AL(t)=A(a+bt)A|_L(t) = A(a + b t).

    • Check whether AL(t)A|_L(t) has degree at most mHm|H|.

  • Reasoning: If AA is of low total degree, then its restriction to any line is a low-degree univariate polynomial.


Step 2: Testing that Each AiA_i is of Low Degree

  • Objective: Verify that each AiA_i has total degree at most dd.

  • Method: For each ii:

    • Randomly select a line LL in F3m+1\mathbb{F}^{3m+1}.
    • Restrict AiA_i to LL to obtain AiL(t)=Ai(a+bt)A_i|_L(t) = A_i(a + b t).
    • Check whether AiL(t)A_i|_L(t) has degree at most dd.

Step 3: Testing Consistency Between AiA_i and Ai1A_{i-1}

  • Objective: Verify that AiA_i and Ai1A_{i-1} agree on Fi1HF3m+1i\mathbb{F}^{i-1} H \mathbb{F}^{3m+1 - i}.

  • Method:

    • For each i[1,3m+1]i \in [1, 3m+1]:

      • Randomly select:

        • r=(r1,,ri1)Fi1r' = (r_1, \dots, r_{i-1}) \in \mathbb{F}^{i-1}
        • r=(ri+1,,r3m+1)F3m+1ir'' = (r_{i+1}, \dots, r_{3m+1}) \in \mathbb{F}^{3m+1 - i}
        • eHe \in H
      • Evaluate:

        • Ai1(r,e,r)A_{i-1}(r', e, r'')
        • Ai(r,e,r)A_i(r', e, r'')
      • Consistency Check: Accept if Ai1(r,e,r)=Ai(r,e,r)A_{i-1}(r', e, r'') = A_i(r', e, r'').

  • Additional Low-Degree Test:

    • Restrict AiA_i to the axis-parallel line:

      L={(r,t,r)tF}L = \{ (r', t, r'') \mid t \in \mathbb{F} \}
    • Check that AiL(t)A_i|_L(t) is a univariate polynomial of degree at most dd.

  • Reasoning:

    • Ensuring that AiA_i and Ai1A_{i-1} agree on Fi1HF3m+1i\mathbb{F}^{i-1} H \mathbb{F}^{3m+1 - i} helps propagate the vanishing property from AiA_i to Ai1A_{i-1}.
    • By induction, if A3m+1A_{3m+1} vanishes on F3m+1\mathbb{F}^{3m+1} and the polynomials are consistent, then A0A_0 vanishes on H3m+1H^{3m+1}.

Step 4: Testing that A3m+1A_{3m+1} Vanishes on F3m+1\mathbb{F}^{3m+1}

  • Objective: Verify that A3m+1(r)=0A_{3m+1}(r) = 0 for all rF3m+1r \in \mathbb{F}^{3m+1}.

  • Method:

    • Randomly select rF3m+1r \in \mathbb{F}^{3m+1}.
    • Evaluate A3m+1(r)A_{3m+1}(r).
    • Zero Test: Accept if A3m+1(r)=0A_{3m+1}(r) = 0.
  • Reasoning:

    • Since A0(x,y,z,τ)=P(x,z,y,τ,A(x),A(y),A(z))A_0(x, y, z, \tau) = P\big(x, z, y, \tau, A(x), A(y), A(z)\big), this shows that PP satisfies the vanishing condition when composed with AA.

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: A3m+1A_{3m+1} vanishes on F3m+1\mathbb{F}^{3m+1} by direct testing.
  • Inductive Step: If AiA_i vanishes on FiH3m+1i\mathbb{F}^i H^{3m+1 - i} and AiA_i agrees with Ai1A_{i-1} on Fi1HF3m+1i\mathbb{F}^{i-1} H \mathbb{F}^{3m+1 - i}, then Ai1A_{i-1} vanishes on Fi1H3m+1(i1)\mathbb{F}^{i-1} H^{3m+1 - (i-1)}.

By induction, A0A_0 vanishes on H3m+1H^{3m+1}, which is the desired property. Since A0(x,y,z,τ)=P(x,z,y,τ,A(x),A(y),A(z))A_0(x, y, z, \tau) = P\big(x, z, y, \tau, A(x), A(y), A(z)\big), this shows that PP satisfies the vanishing condition when composed with AA.

Query Complexity

  • Oracle Length:

    • The oracle (proof) includes:

      • The evaluations of AA over Fm\mathbb{F}^m: Fm|\mathbb{F}|^m entries.
      • The evaluations of each AiA_i over F3m+1\mathbb{F}^{3m+1}: (3m+1)F3m+1(3m + 1) \cdot |\mathbb{F}|^{3m+1} entries.
    • Total Length:

      Fm+(3m+1)F3m+1=O(mF3m+1)|\mathbb{F}|^m + (3m + 1) \cdot |\mathbb{F}|^{3m+1} = O(m \cdot |\mathbb{F}|^{3m+1})
  • Query Complexity:

    • The verifier makes queries when performing:

      • Low-degree tests on AA and each AiA_i.
      • Consistency checks between AiA_i and Ai1A_{i-1}.
      • Zero tests on A3m+1A_{3m+1}.
    • Total Queries:

      • Each low-degree test involves querying points along random lines, typically O(1)O(1) points per line.
      • The number of lines tested is O(1)O(1) per polynomial.
      • For O(m)O(m) polynomials, the total queries are O(m)O(m).
      • The consistency checks involve querying AiA_i and Ai1A_{i-1} at random points, adding O(m)O(m) more queries.
    • Total Query Complexity:

      O(mF)O(m \cdot |\mathbb{F}|)

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

  1. O. Goldreich, Introduction to Property Testing. Cambridge: Cambridge University Press, 2017.

  2. 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.