There is an algorithmic problem $A(n)$, where $n$ is the size of the problem. It is known that, for every candidate solution S, the time it takes to verify whether it is a correct solution to $A(n)$ is $T(n)$.Does this imply a lower bound on the time it takes to find a correct solution to $A(n)$ (e.g. that it takes at least time $T(n)$)? This seems obvious to me, but obvious and true do not always coincide. Since $P \subseteq NP$, the implication probably holds if $T(n)$ means polynomial time. But does it hold in general, for arbitrary complexity classes?Does this imply any upper bound on the time it takes to the time it takes to find a correct solution to $A(n)$ (e.g. that it can be done in time $2^{T(n)}$)?
Verifying a solution vs. finding one
complexity theory;runtime analysis
You should define carefully what it means to find a correct solution. In trivial problems, this may be different than verifying. For example, consider the problem of deciding whether a graph is colorable in some number of colors. This problem is trivial, since every graph is colorable in $|V|$ colors. Moreover, it is easy to define such a coloring - give a distinct color for each vertex.However, verifying that a coloring is correct takes quadratic time.As for an upper bound - if verifying a solution takes time $T(n)$, than going over all solutions will take time $2^{O(T(n))}$, so not exactly $2^{T(n)}$, but close.