You dont just need easy to verify, you need easy to fairly distribute the problem instances.
Take primes. How do you know the person generated new primes and didnt just have a bunch saved up? With hashes you have to hash the current block which is unpredictable, and also means as time goes on it gets harder and harder to have a competing chain, because you dont just have to solve the current block but also be better for all the preceeding chains.
Additionally NP-complete problems are hard because the average complexity tends not to be super hard, which is a major sticking point in this application. So you have to somehow verify the person is solving a hard instance of the problem and not an easy instance.
Take primes. How do you know the person generated new primes and didnt just have a bunch saved up? With hashes you have to hash the current block which is unpredictable, and also means as time goes on it gets harder and harder to have a competing chain, because you dont just have to solve the current block but also be better for all the preceeding chains.
Additionally NP-complete problems are hard because the average complexity tends not to be super hard, which is a major sticking point in this application. So you have to somehow verify the person is solving a hard instance of the problem and not an easy instance.