3 ms·
Linear in the size of the witness, however many bits it takes to express it.
by andrewla 2y ago
Linear in the size of the witness, however many bits it takes to express it.
- trixthethird 2y agoThis applies to any computable problem though, no? At minimum the verifier has to read the witness. If we ignore PCPs and such. The point here is that the witness grows very fast in terms of vector dimensionality and/or move set size.