<p>Let us consider the following problem:</p>

<ul>
<li>Instance: A Turing machine $M$. A word $w$.</li>
<li>Feasible solutions: (i) The word $ww$. (ii) The word $w$, in case $M$ accepts $w$.</li>
</ul>

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

CC BY-SA 3.0
2017-05-12T08:14:44.927Z
2017-05-12T09:01:56.340Z
2017-05-12T09:01:56.340Z
Gamow
<p>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?</p>

CC BY-SA 3.0
2017-05-11T13:31:57.050Z
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.
Sasho Nikolov
CC BY-SA 3.0
2017-05-11T14:15:38.090Z
No I mean, deterministically... I will go and update it.
and are they quite common in literature?
Dont they seem counter-intuitive.
Vk1
CC BY-SA 3.0
2017-05-11T14:19:40.590Z
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.
Gamow
CC BY-SA 3.0
2017-05-11T14:35:02.600Z
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).
Emil Jeřábek
CC BY-SA 3.0
2017-05-11T16:38:47.163Z
The answer has to be no if you have the same deterministic algorithm that was used to generate the solution you're considering, as one can always just run that algorithm, see that you get the same answer, and return. The runtime is asymptotically identical. I think the only way to get around this would be tricks like Gamow's - problems that include a trivial solution, but other more interesting solutions exist.
Artimis Fowl
CC BY-SA 3.0
2017-05-11T17:25:10.853Z
Okay, i will edit the question to say "non-trivial" solutions, otherwise question wont make sense.

Emil and artimis are giving contradicting answers...
I request both of u read the question clearly,
Vk1
CC BY-SA 3.0
2017-05-11T20:16:40.233Z
@RickyDemer- Please read the comments, u will get the context.
Vk1
CC BY-SA 3.0
2017-05-11T21:38:27.763Z
Does FPTAS for permanent work?
Turbo
<ds.algorithms><complexity-classes>
Is finding a solution harder than verifying a solution?
Vk1
# Is finding a solution harder than verifying a solution?

(Asked by: username_0 on 2017-05-11)

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?

**Tags:** ds.algorithms, complexity-classes

> **Comments:**
> **username_1**: 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.  
> **username_0**: No I mean, deterministically... I will go and update it. and are they quite common in literature? Dont they seem counter-intuitive.  
> **username_2**: 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.  
> **username_3**: 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).  
> **username_4**: The answer has to be no if you have the same deterministic algorithm that was used to generate the solution you're considering, as one can always just run that algorithm, see that you get the same answer, and return. The runtime is asymptotically identical. I think the only way to get around this would be tricks like username_2's - problems that include a trivial solution, but other more interesting solutions exist.  
> **username_0**: Okay, i will edit the question to say "non-trivial" solutions, otherwise question wont make sense.  Emil and artimis are giving contradicting answers... I request both of u read the question clearly,  
> **username_0**: @RickyDemer- Please read the comments, u will get the context.  
> **username_5**: Does FPTAS for permanent work?  

---

## 1 answers

### Answer by username_2 on 2017-05-12. Score: 4

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.


---

