19.3 The conditional algorithmic consequence
On this page · Permalink · Source line 593
Lemma 19.4: Finite-field root bound
If a nonzero polynomial \(P\in K[z_1,\ldots,z_m]\) has total degree at most \(d\), where \(K\) is finite, then
Proof
Induct on the number of variables. For one variable this is the elementary root bound. In the inductive step, write
The leading coefficient has total degree at most \(d-r\), so it vanishes at a random first \((m-1)\)-tuple with probability at most \((d-r)/|K|\). Otherwise the remaining univariate polynomial is nonzero with at most \(r\) roots. The union bound gives \((d-r+r)/|K|=d/|K|\).
Proposition 19.5: Conditional randomized satisfiability test
Suppose the weighted expression in (19.1) can be evaluated exactly and uniformly in time polynomial in the verifier description and witness length, over explicitly represented characteristic-two fields of polynomial size. Then choosing \(|K|\ge4m\) gives a one-sided randomized polynomial-time satisfiability test. It never accepts an unsatisfiable verifier and accepts a satisfiable one with probability at least \(3/4\) per evaluation.
Proof
Choose a uniformly random \(z\in K^m\), evaluate \(P_R(z)\) under the assumed algorithm, and accept when it is nonzero. If no witness accepts, Theorem 19.1 makes the polynomial zero identically, so there is no false acceptance. Otherwise Lemma 19.4 bounds the rejection probability by \(m/|K|\le1/4\). A field of polynomial size uses \(O(\log m)\) bits per element, so the random input has \(O(m\log m)\) bits. Under the explicit efficient-field and evaluator hypotheses, the procedure has polynomial running time.
Conditional means the evaluator is still missing
The proposition assumes a uniform efficient evaluator that has not been constructed here. The implemented evaluator is exponential. Even with the assumed evaluator, the stated conclusion is randomized with one-sided error, not a deterministic proof of \(P=NP\).
The exact tests use \(\mathrm{GF}(16)={\mathbb F_2}[t]/(t^4+t+1)\). They evaluate every specified verifier through three witness bits at every field point, while the independent top-coefficient check uses all field points through two witness bits and the declared smaller coordinate grid at three bits. These domains must not be conflated.