Hashing with (some sort of) Public and Private keys/salt/nonce
What you are describing here looks like a thing, indeed. For instance, in the case of passwords, you have human-created password, whose entropy is generally weak and who are often found in dictionaries...

So, suppose you'd like to store the user's password in your database in a way that would prevent an attacker obtaining the database to deduce the actual password used by any given user, the simplest way around it might be to simply hash the passwords and store the hashes, right?

Well, if you just hash the passwords, then an attacker could simply take a dictionary and hash its content and compare it to the hashes he found in your database... So it wouldn't prevent the adversary to possibly find some passwords.

So, the next step is obviously to salt the hashes you are storing, in order to increase the cost of the dictionary attack for your adversary. And you can even use a different salt for each password, thus increasing the cost of a dictionary attack even more.

Note that modern hash functions, such as Blake2, sometimes includes support for salted and even for keyed hashing out of the box.    

Modern password hashing algorithm, such as Argon2 are actually very similar to "proof of work", as you noticed, since you want to make your adversary consume as much time and power as possible. 

There are also other cases where you'd want something like this (see how HMAC works, for instance.)