<p>There certainly is significance -- and there is a lot that is known about the subject.</p>
<p>If you are willing to make reasonable assumptions, such as the security of cryptographic primitive, then it is straightforward to achieve such a ratio: any secure encryption scheme will provide one example.  Encrypting takes polynomial time if you know the key, while recovering the key if you don't know it takes super-polynomial time (assuming the encryption scheme is secure), so their ratio tends to 0 as the security parameter goes to infinity.</p>
<p>If you want to avoid making any unproven assumptions, then I believe it is an open problem to find such a problem.  In particular, it is an open problem to prove that give an explicit example of a function on <span class="math-container">$n$</span> bits such that it takes a circuit of size more than <span class="math-container">$5n$</span> to compute the circuit.  See e.g., <a href="https://cstheory.stackexchange.com/q/7388/5038">Is there a better than linear lower bound for factoring and discrete log?</a>.  This corresponds to a constant (strictly greater than zero) ratio.  So, I don't think it is known how to exhibit a problem such that it provably has a ratio that goes to zero in the limit.</p>

CC BY-SA 4.0
2020-09-08T00:19:44.337Z
The $5n$ is not for arbitrary problems — you can prove for that for a random function, it takes exponential size circuits (and quite a few related results). What we can't do is identify a *specific* function for which we can prove there's a circuit that takes more than $5n$ gates.
Peter Shor 
CC BY-SA 4.0
2020-09-08T01:51:54.413Z
@PeterShor, absolutely, thank you for the correction!  I was sloppy in my statements in my answer.  I've revised my answer and I hope it addresses that point.
D.W.
CC BY-SA 4.0
2020-09-07T23:46:09.933Z
2020-09-08T01:51:35.970Z
2020-09-08T01:51:35.970Z
D.W.
<p>I believe I have found a problem, the solution to which can be verified in 0 time (the solution can only be located in non-zero time, however).  As a result, the ratio of the time required to locate a solution to the problem over the time required to verify its solution is infinite.  I was wondering if this ratio generally has significance in computer science.</p>

CC BY-SA 4.0
2020-09-07T00:30:47.390Z
https://en.wikipedia.org/wiki/Merkle%27s_Puzzles
D.W.
CC BY-SA 4.0
2020-09-07T00:47:41.137Z
@D.W. 's posting of the above link implies, I think, an answer of No to my question, though the article linked doesn't expressly touch upon the ratio above.
Francis J. Merrick
CC BY-SA 4.0
2020-09-07T01:07:44.830Z
In usual computational models, the time taken to "read" the solution counts towards verification time. Hence nothing can be computed nor verified in 0 time.
Watercrystal
<complexity>
Is there significance to the ratio of the time it takes to locate a problem's solution over the time it takes to verify the solution?
Francis J. Merrick
# Is there significance to the ratio of the time it takes to locate a problem's solution over the time it takes to verify the solution?

(Asked by: username_0 on 2020-09-07)

I believe I have found a problem, the solution to which can be verified in 0 time (the solution can only be located in non-zero time, however). As a result, the ratio of the time required to locate a solution to the problem over the time required to verify its solution is infinite. I was wondering if this ratio generally has significance in computer science.

**Tags:** complexity
> **Comments:**
> **username_1**: https://en.wikipedia.org/wiki/Merkle%27s_Puzzles  
> **username_0**: @D.W. 's posting of the above link implies, I think, an answer of No to my question, though the article linked doesn't expressly touch upon the ratio above.  
> **username_2**: In usual computational models, the time taken to "read" the solution counts towards verification time. Hence nothing can be computed nor verified in 0 time.  

---

## 1 answers

### Answer by username_1 on 2020-09-07. Score: 3

There certainly is significance -- and there is a lot that is known about the subject.

If you are willing to make reasonable assumptions, such as the security of cryptographic primitive, then it is straightforward to achieve such a ratio: any secure encryption scheme will provide one example. Encrypting takes polynomial time if you know the key, while recovering the key if you don't know it takes super-polynomial time (assuming the encryption scheme is secure), so their ratio tends to 0 as the security parameter goes to infinity.

If you want to avoid making any unproven assumptions, then I believe it is an open problem to find such a problem. In particular, it is an open problem to prove that give an explicit example of a function on $n$ bits such that it takes a circuit of size more than $5n$ to compute the circuit. See e.g., [Is there a better than linear lower bound for factoring and discrete log?](https://cstheory.stackexchange.com/q/7388/5038). This corresponds to a constant (strictly greater than zero) ratio. So, I don't think it is known how to exhibit a problem such that it provably has a ratio that goes to zero in the limit.

> **Comments:**
> **username_3**: The $5n$ is not for arbitrary problems — you can prove for that for a random function, it takes exponential size circuits (and quite a few related results). What we can't do is identify a *specific* function for which we can prove there's a circuit that takes more than $5n$ gates.  
> **username_1**: @PeterShor, absolutely, thank you for the correction!  I was sloppy in my statements in my answer.  I've revised my answer and I hope it addresses that point.  

---

