Examples of problems in P but with verifiers with many computations

Question

Let me first specify my question. I am looking for decision problems with polynomial algorithms but such that the simpliest or fastests verifiers do many computations. Here by verifiers I mean both YES and NO verifiers. It might be the case that this is too specific. By "verifiers with many computations" I mean verifiers that use non-trivial computational methods (e.g. dynamic programming, transforms, different methods of computational algebra etc.)

From what I understand most verifiers in $\mathsf{P}$ are either trivial or rely on good characterization theorems but are, themselves, not very complicated algorithms. Is this something to be expected from problems in $\mathsf{P}$? I mean these are the easiest of problems but some have really complicated good characterizations, I would expect that the complexity of the characterization translates somehow to the verifier (but from what I have seen this is not the case).

It might be the case that my question not interesting/stupid but to be honest I cannot see it.

Answer 1

There are none. For every problem in NP, there is a way to build a verifier such that the verifier is very simple and uses only trivial methods.

Proof: Let $L$ be any language in NP. Then it has a verifier $V$, such that $x \in L$ iff $\exists y . V(x,y) = \text{true}$. We call $y$ the certificate or witness.

Now let's construct a new verifier, $V^*$, as follows. The input to $V^*$ is a pair $(x,y^*)$, where the witness $y^*$ has the form $y^*=(y,(s_1,t_1),(s_2,t_2),\dots,(s_k,t_k))$. Here the second part of $y^*$ is the transcript of the execution of $V$ on input $(x,y)$. In particular, if $V$ is a Turing machine, then $s_i$ is the finite state it is in, and $t_i$ is the content of the tape, after the $i$th step of execution. $V^*$ checks whether the transcript is a valid record of an execution starting on input $(x,y)$, and whether it halts with output $\text{true}$.

Now $V^*$ can be implemented by a very simple algorithm, that uses only trivial methods. The algorithm just checks that each step of execution was done correctly (i.e., looks at $(s_i,t_i)$ and $(s_{i-1},t_{i-1})$). This is easy to check, given how simple a Turing machine is. Also, it is efficient. The running time of $V^*$ is at most the square of the running time of $V$.