# 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?

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.

• en.wikipedia.org/wiki/Merkle%27s_Puzzles
– D.W.
Sep 7 '20 at 0:30
• @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. Sep 7 '20 at 0:47
• 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. Sep 7 '20 at 1:07

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?. 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.
• 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. Sep 8 '20 at 0:19