Can we construct problems that can be solved in $\Theta(n^c)$ time, and tested in $O(n)$ time
If you believe in the exponential time hypothesis, then you can construct such an example by padding SAT. The ETH states that solving SAT on $n$ variables takes time $2^{\Omega(n)}$; let's say the time is $T(n)$. We can assume that SAT instances consist of at most $O(n^3)$ clauses, and so have length at most $\tilde{O}(n^3)$. Pad such an instance by adding $N = T(n)^{1/c}$ (where $c &gt; 1$ need not be an integer) spaces. According to the ETH, the resulting languages requires time $\Omega(n^c)$ to solve in the worst case (the "best case" time complexity of a problem is almost always $\tilde{O}(n)$, depending on your model of computation and how devious the problem is), but witnesses can be verified in time $\tilde{O}(n)$ and $O(\log n)$ space; most of these resources are spent on checking that the input is well-formed.

The same idea would work even with much weaker hypothesis, such as P$\neq$NP; I'll leave you the details.