1
$\begingroup$

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.

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

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 8 '20 at 0:19
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Sep 8 '20 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.