-3
$\begingroup$

Is there any known problem in Comp science where determinisitically finding a "non-trivial" solution to that problem is asymptotically easier than verifying a solution?

$\endgroup$
10
  • $\begingroup$ It depends what exactly you mean. There are many examples where a simple randomized algorithm succeeds with high probability but we do not know any way to verify that the algorithm has succeeded. For example a random Gaussian matrix satisfies the RIP property with high probability but we do not know an efficient algorithm to test for this property. $\endgroup$ May 11, 2017 at 13:31
  • 2
    $\begingroup$ What about: "Given a positive integer $n$, find a divisor $d$ of $n$." Finding a solution (for instance the divisor $d=1$) can be trivially done in constant time $O(1)$, without even looking at the input. But for verifying that some arbitrary integer $d$ is indeed a divisor of $n$, one has to read the input and hence needs at least $\Omega(\log n)$ time. $\endgroup$
    – Gamow
    May 11, 2017 at 14:19
  • 1
    $\begingroup$ Any NP problem outside P. Actually, depending on what exactly you mean by “asymptotically easier”, any NP problem outside coNLOGTIME (plenty of those are known, unconditionally). $\endgroup$ May 11, 2017 at 14:35
  • 1
    $\begingroup$ How do you define ​ "non-trivial" ​ for your question? ​ ​ ​ ​ $\endgroup$
    – user6973
    May 11, 2017 at 19:17
  • 2
    $\begingroup$ I have now read the comments and get the context, but still lack an answer to my question. ​ ​ $\endgroup$
    – user6973
    May 11, 2017 at 20:39

1 Answer 1

4
$\begingroup$

Let us consider the following problem:

  • Instance: A Turing machine $M$. A word $w$.
  • Feasible solutions: (i) The word $ww$. (ii) The word $w$, in case $M$ accepts $w$.

(1) Now finding a solution is very easy: Simply output the word $ww$ in linear time.
(2) On the other hand, deciding whether the word $w$ is a feasible solution for a given instance is an undecidable problem.

$\endgroup$

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