Are there interesting examples of (systems) of equations where it is known to be harder to find a solution (in terms of scaling with respect to problem size) than verifying a provided solution for correctness?
A non-expert may find it surprising that Stein, Riccati, Sylvester matrix equations with $d\times d$ matrices all have the same $O(d^3)$ complexity for solving as for verifying, wondering if this is a rule that holds more generally.