1

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.

Francis J. Merrick
  • 19
  • 2
  • https://en.wikipedia.org/wiki/Merkle%27s_Puzzles – D.W. Sep 07 '20 at 00: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. – Francis J. Merrick Sep 07 '20 at 00:47
  • 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. – Watercrystal Sep 07 '20 at 01:07

1 Answers1

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

D.W.
  • 12,054
  • 2
  • 34
  • 80
  • 1
    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 Sep 08 '20 at 00: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 08 '20 at 01:51