As long as your problem can be defined entirely by data from the previous block and there is a nonce you can vary you can adopt proof of work to just about anyt

As long as your problem can be defined entirely by data from the previous block and there is a nonce you can vary you can adopt proof of work to just about anything. The problem is that for most problems you don't want to explore the space of potential problems randomly, you want to select ones that people care about. If you allow an actor to dictate what problem to work on then you can have that actor pick a problem they have already solved and will be able to roll back tx arbitrarily once they have control.