Witnesses

Si se quiere probar una propiedad C, muchas veces se puede encontrar otra propiedad D que es cierto (resp. falso) con gran probabilidad si C es cierto (resp. falso) y además mucho más facil de verificar. En caso de poder acotar arbitrariamente el error de equivocarse, se va a verificar D en lugar de C.

Por ejemplo, se quiere verificar si un polinomio es idéntico a cero o no, donde f() es definido de una manera indirecta. En lugar de probarlo formalmente, se checa si para ciertas a_i. Una implementación será:

Dado , el grado d y k;
Define .
Repeat k veces:
elige arbitrariamente de I
Calcula ;
Si no es cero, termina y concluye que f() no es idéntico 0;
end repeat
Concluye que f() es idéntico 0.

La probabilidad de equivocarse depende del número de ceros de f() en el intervalo (tarea!). Con este fin se puede usar la propiedad: