1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – PleaseHelp Feb 8 '15 at 8:05
  • $\begingroup$ I just found this question, which looks identical: cs.stackexchange.com/questions/4619/… $\endgroup$ – Erel Segal-Halevi Feb 9 '15 at 6:02
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Erel Segal-Halevi Feb 8 '15 at 17:02
  • $\begingroup$ 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. $\endgroup$ – Shaull Feb 8 '15 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.