Verifiable Delay Functions
Boneh et al. have recently introduced this concept
https://eprint.iacr.org/2018/601.pdf . Shortly, these are functions that guaranteely require certain amount of time to be computed even if parallelism is available, and the output can be easily verified for correctness. For example, a Bitcoin proof of work is not a VDF because it can be (and is) computed quickly by a number of parallel processors. This concept has many practical applications for decentralized protocols such as randomness beacon: participants bring their seeds within time T then apply VDF G to the collection. The result can not be manipulated by any party if G can not be computed faster than T.
Interestingly, one can not obtain such functions if parallelism is unlimited: if both input and output are short, the solution search is an NP problem and we do not know any computation that requires exponential (of input) time, even if we drop the fast verification requirement. Also the solution can be brute forced by an exponential number of processors.
The authors suggest several VDF candidates for bounded parallelism. First, one can obtain a VDF by applying a ZKSNARK proof generation algorithm to a sequence of hash function calls. In the straightforward setting the function is too slow, but it can be sped up using incremental proofs of computation. Secondly, a polynomial GCD of degree t is a candidate if less than t^2 processors are available. There are also some other underexplored candidates, but no definitively good one.
One may wonder if some memory-hard functions such as our Equihash or MTP are good VDF. Unfortunately, the MTP computation is inherently parallel even though we tried to make it as memory-hard as possible by using a large instance of Argon2, thus making it difficult for ASIC implementation. Equihash is more promising as long as the parallelism is bounded: the bottleneck of Equihash is sorting, and there are well known logarithmic parallel sorting algorithms, though they are all very difficult for practical implementation on any architecture. When a more practical mesh architecture is considered, we are aware of a parallel algorithm that sorts N inputs in sqrt(N) time with N^2 processors. The delay is present but it is sublinear. It remains to see if other candidates appear.