# 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, 2020 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, 2020 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, 2020 at 1:07

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?. 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, 2020 at 0:19
• @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.
Sep 8, 2020 at 1:51