[andrewla]

Linear in the size of the witness, however many bits it takes to express it.

[trixthethird]

This 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.