The verifier doesn't need to be deterministic, just to output a proof artifact that can be independently validated for correctness.