Verifying a solution vs. finding one

Question

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)$.

1. 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?

2. 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)}$)?

• PleaseHelp: If you could find a solution in lesser time then, to verify a candidate solution S you could simply find all solutions and compare it. Now, comparison would take time T(no.of solutions) at the worst case of S being the last solution and assuming that comparison can be done in constant time.
• Erel Segal-Halevi: I just found this question, which looks identical: cs.stackexchange.com/questions/4619/…

Answer 1

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.

• Erel Segal-Halevi: Thanks! The first part is convincing. I didn't understand the second part: why 2ドル^{O(T(n))}$? Is it obvious that the number of solutions is finite at all?
• Shaull: If, given input of size $n,ドル it takes $T(n)$ time verifying a solution $S,ドル then a verifier can only read at most $T(n)$ bits from $S$. Thus, if there is some witness, there is also one of size at most $T(n)$. So it's irrelevant whether the number of solutions is finite, all you need is that there is a bound on a minimal-length witness.