For which problems in P is it easier to verify the result than to find it?

For (search versions) of NP -complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) exponential time. In P, however, the solution can also be found in polynomial time, so it does not seem obvious when is the verification faster than finding the solution. In fact, different problems seem to behave differently from this point of view. Some examples: 3SUM: given $n$ input numbers, find 3 among them that sum to 0. As far as I know, the fastest known algorithm runs in $O(n^{2-o(1)})$ time, and this order is conjectured optimal. On the other hand, the verification of a solution is much faster, since all we need to do is just to check that the 3 found numbers indeed sum to 0. All-Pairs Shortest Paths: given a graph with edge weights, compute its shortest path distance matrix. Once such a matrix is given, can it be checked faster that it is indeed the correct distance matrix, than re-computing it? My guess is that the answer is perhaps yes, but it is certainly less obvious than for 3SUM. Linear Programming. If a claimed optimal solution is given, checking it is easier than re-computing it, when auxiliary information is also given (an optimal dual solution). On the other hand, if only the primal solution is available, it is not clear if one can check it faster, than actually solving the LP. Question: what is known about this subject? That is, when is it easier to verify a solution for a problem in P, than finding the solution?