[JD557]

I thought about this as well before, but the problem is that you don't want just ANY NP-problem: You want an NP problem (it doesn't even have to be NP-complete) that you can easily adjust the difficulty.

How do you adjust the difficulty on something like this?

Also, you always have to calculate the "hashes" of the blocks. I guess you could encode a block as a graph and it's "hash" could be the smallest path that visited all the edges, but how useful would that be?

When I looked into this in the past, I stumbled into Gridcoin[1], but I don't know how they deal with the difficulty/usefulness of the solutions.

[1]: https://www.gridcoin.us/

[tradedash]

Thanks for the link. I'll look into it!

> you can easily adjust the difficulty.

For Prime Factorization for instance, which like you say, isn't even NP-complete. You can easily adjust the difficulty by increasing the size of the number in question.

[JD557]

I'm not sure if that's completely true for prime factorization. There are numbers that are larger, yet easier to factorize.

For example, I think that a power of two, like 1024, is much faster to factorize than, let's say, 1001 (71113). (I'm not quite sure this example is true)

Here's a more detailed description: https://mathoverflow.net/questions/249266/classes-of-numbers...

[Geforce8472]

Gridcoin relies on BOINC for the work distribution, essentially you get credit based on how long it took you to complete the task (to prevent cheating most projects rely on a quorum of results being the same (each task is sent to several users)).

This is not used as a direct mining mechanism, the blockchain is secured using Proof of Stake rather than Proof of Work.