# Is finding a solution harder than verifying a solution? [closed]

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?

• 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. May 11, 2017 at 13:31
• 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. May 11, 2017 at 14:19
• 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). May 11, 2017 at 14:35
• How do you define ​ "non-trivial" ​ for your question? ​ ​ ​ ​
– user6973
May 11, 2017 at 19:17
• I have now read the comments and get the context, but still lack an answer to my question. ​ ​
– user6973
May 11, 2017 at 20:39

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.