a short round up of the categories for generating proofs of work
Proof of work historically started with CPU implementations, then with GPU and then with increasingly more efficient ASICS thanks to shrinking and optimizations, unless the algorithm is designed to be somewhat resistant which means it can try to saturate something which functions as the bottleneck to prevent benefitting from further optimizations.
Some notable bottlenecks ideas and applications:
Memory hard and bound: hardness is easier but tech progession makes it a poor long term choice, whereas being bound by latency means having a physical limit to the possible improvements, but it is harder to design and is linked to the complexity of the algorithm. [Memory hard schemes] like Yescrypt, Argon2, Lyra2 have been used for proof of work, dagger-hashimoto and ethhash are also memory hard. There aren't really applications in the wild for memory bound algorithms, apart for proof of storage, except that in this case, the lookup is the target and not just a useful property of hashing alghorithm, because proofs in this case are based on challenge/response protocols (..since you have to prove that you are storing something and not just pretending to store it..)
Bandwidth bound: moving data across places is limited to the capacity of the channel used. Implementing a bandwidth bound algorithm means streaming data and applying a (simple!) filter over it to discover useful patterns, the strength of the algorithm depends on the inability of an attacker to predict indexes where the desired data might be located. The only implementations that I know of is found in snowblossom where a progressively huge database generated with a lot of entropy is used as the base. The downside of being bandwidth bound is that it is friendly to scaling, that is the ability to stack and pile hardware to achieve industrial level capacities.
Complexity bound: this is a very hand wavy definition to say that it is hard to optimize against something which appears random ... at least on the surface. If you have some logic that produces a desired output, and you are trying to optimize such logic, you can only do that if you can predict the behavior of the logic to for example cache values, or create fast pipelines for known to recur subroutines; this means that the algorithm strength depends and its ability to fake randomness. As example the idea of smart contracts mining, or any other algorithm that fetches data from a blockchain. [RandomX] as used in monero uses as seed the hash of ~50 blocks behind, a precursor of randomX can be found in cryptonight-adaptive or randomjs. Randomness is only one part of the implementation, the other is to tune the probability distribution to match the capabilities (e.g. instructions set) of the desired target machine, in the case of randomx it is a common CPU architecture, for progpow it is a (nvidia? :P) GPU, in the case of smart contracts mining logic mirroring is not sought since optimizations of the underlying process have dripping utility.
Execution bound: or time bound, generally means requiring some information to produce some information, of course sequentiality (as in repeating the same thing multiple times) is a primitive of all things crypto and is used in most (all?) ciphers since it is the most direct (and obvious) way to trade computation for obfuscation. When utilizing this concept at a lower level (to create a non parallelizable hashing function), the algorithm must be as simple as possible, like a very short mathematical operation, such that the possibility of splitting work through concurrent processes is minimized. [VDF]s achieve this, although, even without the setup requirements, such schemes are deterministic which means that "the fastest always wins", that's why a VDF can only be considered as POW if an implementation is known (proved?) to not be improvable by more than the Δ (delta) delay of communication of the system which intends to use it (e.g. a p2p network). Any algorithm that targets execution boundness without a trapdoor means a 1:1 computation between prover and verifier, but it is not deterministic, which is a requirement (I dare to say..) for POW. [Unprll] was a coin using sequential hashing, hashes verification was partial (1/8?), to improve the verification/prover ratio above 1. Another coin that appears to use sequential hashing is pascalcoin with a mix of memory hardness.
