Randomized detection is conditional on efficient evaluation
On this page · Permalink · Source line 716
The witness polynomial has total degree at most \(m\). Over a finite field \(K\), a nonzero polynomial of total degree at most \(m\) vanishes on at most an \(m/|K|\) fraction of independent uniform field points. The standard inductive proof separates the leading coefficient in the last variable and applies the univariate root bound.
If a uniform polynomial-time exact evaluator for the weighted trace were available, with efficient field representation and arithmetic and \(|K|\ge4m\), one evaluation would accept a satisfiable verifier with probability at least \(3/4\). An unsatisfiable verifier has the zero polynomial, so it never produces a false acceptance. Repetition with independent samples reduces the false-rejection probability to at most \(4^{-r}\) after \(r\) trials.
| Witness bits | GF(16) points | maximum zeros in source tests | degree-bound zeros |
|---|---|---|---|
| 1 | 16 | 1 | 1 |
| 2 | 256 | 31 | 32 |
| 3 | 4,096 | 721 | 768 |
These source tests enumerate every verifier at each displayed witness length and all field points for the polynomial evaluations. The independent coefficient-extraction comparison has a narrower three-variable grid: coordinates \(0,1,2,3\), rather than all GF(16) points. Both scopes are recorded.
This is a conditional randomized algorithmic implication. The required efficient trace evaluator is not supplied. The existing exact evaluator is exponential in witness length, and no deterministic \(P=NP\) conclusion is drawn. Random bits and polynomial output description alone do not account for the evaluation operation.