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.

Can’t you have the chain do multiple random verifications before accepting it?

Finding prime numbers, even very large ones, is neither difficult nor useful; there are simple algorithms for determining the primality of a number which don't require extraordinary amounts of computing power to execute.

Even factoring large semiprimes isn't inherently useful -- it's an interesting mathematical exercise, but isn't a goal unto itself.