The value of the currency would never go below the value of the solution to one of those random problems. Say I have an NP-complete problem to solve. I can solve it myself, or I can pay you to solve it for me. Or, I can (as is guaranteed by the definition of NP-completeness) translate it into an instance of the NP-complete problem that this cryptocurrency is based on, and post a special transaction that awards coins to the first person to provide a solution to this NP-complete problem. (Here's a possible weakness: when you go to announce your solution, what stops another node stealing it? In Bitcoin I think this is handled by having the address that generated/fee coins go to as part of the data being hashed, but it seems like it would be difficult to make the solution to e.g. the Traveling Salesman Problem depend sufficiently on these parameters and also be useful as a solution to the original problem. But assume we can solve this, for the sake of the economic argument.) Then, the value of your currency would never go below the value of having one of this class of NP-complete problems solved for you, because you could always bid above the auto-generated problems and have all rational miners work on your problem.