Or more generally, is there a function or algorithm that is slow to calculate/execute, has a reliable execution time, and has a result that can be tested much more quickly than the calculation took?


It sounds like you're looking for a proof-of-work system.

One way to implement such a system would be, given a message $m$, to ask for a suffix $s$ such that the hash $H(m \operatorname{\|} s)$, where $H$ is some standard cryptographic hash function and $\|$ denotes concatenation, begins with a specific prefix (e.g. $n$ zero bits).

Of course, the execution time of such a scheme is not really deterministic; we can predict the expected time it will take, but the actual time will be geometrically distributed, and so will vary a lot. Also, the particular scheme I described is very easy to parallelize, so that using multiple processors (or parallel processors like GPGPUs) cuts down the expected solving time in inverse proportion to number of cores used. Depending on your application, this may or may not be an issue.

  • $\begingroup$ This is precisely how Bitcoin mining works (except it's not a suffix, it's embedded in the block). It takes a lot of work to mine a block but very little work to confirm a validly-mined block. $\endgroup$ – David Schwartz Apr 14 '12 at 4:07

The wide class of NP problems meets your general question, almost to the exact definition. The summary is that (we conjecture that) there are problems that cannot be solved in as little as polynomial time but have solutions that can be verified to be correct in just polynomial time, so solving for the answer takes much longer than verifying the answer is correct. Example: Factoring a large number into its integer prime factors is computationally slow, but given those prime factors it is easy to verify that they multiply to the original number. (There are many other examples.)

We generally use these kinds of problems in cryptographic constructions such that the user with the message or key calculates the easy part and the hard part is published to the world. We choose the answer, from the answer derive the hard problem, then we publish the hard problem. But it sounds like you want the opposite of that, namely, a hard problem that we output the answer for, which others then verify. Ilmari's answer provided an example of that: If the hash used is a good one-way function, then it is exponential time to find the answer $s$, but it is polynomial time to verify that $s$ is correct.

Regarding "reliable" execution time: We generally accept very high probabilities as sufficient for "reliable". You need to decide if your time constraint should be the average or should be the minimum. If it's the minimum, then you should choose a work factor that gives an average that is much larger than the minimum and results in attampts taking longer than the minimum wih high probability.

(For the record, it does not seem like what you are asking for is an actual cryptographic hash function; but you may be able to use one to build what you want.)

  • 1
    $\begingroup$ I think you mean NP hard problems, not just NP problems (which include all easy problems, too). $\endgroup$ – Paŭlo Ebermann Apr 11 '12 at 21:41

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.