I can not find an example problem space where the complexity (time) of verifying the solution is greater than that of solving the problem.
But I was hoping there would be a formal proof of this out there.
3
-
$\begingroup$ What do you call the "complexity of the solution"? $\endgroup$– Yves DaoustCommented Sep 18 at 15:24
-
$\begingroup$ @YvesDaoust the time complexity (big-o) of the given solution, eg: 2d convex hull is O(nlogn) $\endgroup$– Penny DreudterCommented Sep 18 at 18:41
-
1$\begingroup$ Do you allow randomized algorithms? If so, consider, the problem of generating a string of high Kolmogorov complexity. A random string of length n has K-complexity at least n/2 with exponentially high probability. But it is not decidable (or even close to decidable) to verify that a string has high K-complexity. $\endgroup$– Neal YoungCommented Sep 19 at 18:37
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
This is possible when a problem has multiple solutions, and the time complexity of generating a single solution is lower than the time complexity of generating all solutions.
For example, consider the problem "generate a Turing Machine that halts on all inputs." You can generate a Turing Machine that halts on all inputs in $O(1)$ time, but to take a given Turing Machine and test if it halts on all inputs is undecidable e.g. $O(\infty$).
If a problem is guaranteed to have at most one solution, then the complexity of verification is never greater than the complexity of generating a solution, because you can make a trivial verifier that is "generate the solution and check if it's exactly equal to the given input," which will be the same time-complexity as the solver, so long as the solve was at least $O(n)$ (e.g. it actually considers its entire input).
answered Sep 18 at 15:51
$\begingroup$
$\endgroup$
Problem: Given k, find a p such that either p=2 or p is a k digit prime.
Finding a solution: p=2 is a solution. Verification: I give you a k digit number. Please verify that k is a prime.
$\begingroup$
$\endgroup$
It depends on what you mean by "problem".
If you're thinking of function problems (i.e. for each input, there's exactly one output), then there isn't any such problem.
If you have "solution" algorithm $A$ that takes input $i$ and computes $f(i)$ in time $T(|i|)$, then you can easily implement a verifier:
verify(i, candidate_solution):
y := A(i)
return candidate_solution == y
Note that for $A$ to output $f(i)$, its time complexity is $\Omega(|f(i)|)$; the verify routine adds a comparison at the end, that can be done in $\Theta(|f(i)|)$; so verify has the same asymptotic complexity as $A$.
